алгоритм по рекуррентному соотношению (ДП) С++ (простой)

[Feld]

Добрый вечер! Есть задача на рекуррентное соотношение или ДП, не получается решить. Буду рад, если поможете.

Стоимость 1250 ? (Цену не знаю, предложите свою)

Язык С++

Теперь к задаче )
Ограничения по времени до 2 секунд, памяти 256мб.
input.txt - входной файл
output.txt - выходной файл

Условие: Ветка представляет собой цепочку из N станций, связанных между собой N − 1 железнодорожным перегоном. Для каждой станции известен её «уровень важности» с точки зрения всеобщего дела обороны Байтланда — число от 1 до 5. Станция ценна тем, что обеспечивает транспортную связь с другими станциями. Поэтому стратегическая значимость отдельно взятой станции считается равной нулю, а значимость цепочки станций определяется как сумма произведений «уровней важности» станций для всех пар в цепочке, связанных прямо или через другие станции. Например, для железнодорожной сети на рисунке (для станций указаны их «уровни важности») стратегическая значимость вычисляется по формуле 2 ⋅ 1 + 2 ⋅ 5 + 2 ⋅ 4 + 1 ⋅ 5 +  1 ⋅  4 + 5 ⋅ 4 = 49.

Входные данные: В первой строке входного файла записаны целые числа N и M, разделённые пробелом, — это количество станций (1 ≤ N ≤ 300) и количество перегонов между станциями (0 ≤ M < N), которые могут быть разрушены. Во второй строке записаны через пробел N целых чисел в диапазоне от 1 до 5 включительно — «уровни важности» станций в порядке их следования вдоль скоростной железной дороги.

Нужно найти минимальное значение стратегической значимости железнодорожной системы с m разрезами. Только число

Что получилось у меня (наверное не нужен, только название файлов)

#include <iostream>
#include <fstream>


//#define SIZE 4

int sizeArray;
int destroyNum;

using namespace std;

int main()
{
    std::ifstream fin("input.txt");
    std::ofstream fout("output.txt");
    
    fin >> sizeArray;
    fin >> destroyNum;
    const int SIZE = sizeArray;
    
    int **dp = new int*[SIZE];
    int **derrArr = new int*[SIZE-1];
    int *ar = new int[SIZE];
    
    for(int i = 0; i < SIZE; i++){
        for(int j = 0; j < SIZE; j++){
            dp[i] = new int[SIZE];
        }
    }
    
    for(int i = 0; i < SIZE-1; i++){
        for(int j = 0; j < SIZE-1; j++){
            derrArr[i] = new int[SIZE-1];
        }
    }
//
//    int dp[SIZE][SIZE];
//    int derrArr[SIZE-1][SIZE-1];
//    int ar[SIZE];
    
    for(int i = 0; i < SIZE; i++) {
        ar[i] = 0;
        for(int j = 0; j < SIZE; j++) {
            dp[i][j] = 0;
        }
    }
    
    for(int i = 0; i < SIZE-1; i++){
        for(int j = 0; j < SIZE-1; j++)
            derrArr[i][j] = -1;
    }
    
    for(int i = 0; i < sizeArray; i++) {
        fin >> ar[i];
    }
    for(int k = 0; k < SIZE-1; k++) {
        for(int i = 0, j = 1+k; i < SIZE-1; i++, j++) {
            if(j < SIZE) {
               dp[i][j] = ar[i] * ar[j] + dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];
            }
        }
    }
    
    
    if(destroyNum == 0) {
        cout << dp[0][sizeArray-1];
        return 0;
    }
    if(destroyNum == sizeArray - 1){
        cout << 0;
        return 0;
    }
    
//    for(int i = 0; i < SIZE; i++){
//        for(int j = 0; j < SIZE; j++){
//            cout << dp[i][j] << "\t";
//        }
//        cout << "\n";
//    }
    
    int min = 30000;
    for(int i = 0; i < SIZE; i++){
        for(int j = 0; j < destroyNum; j++){
            for(int k = 0; k < SIZE-1; k++){
                derrArr[i+j][k] = dp[i][k];
                if(k+1+j < SIZE)
                    derrArr[i+j][k] += dp[k+1+j][SIZE-1];
                
                if(min > derrArr[i+j][k])
                    min = derrArr[i+j][k];
                
            }
        }
        cout << min;
        break;
    }

    
    
    cout << "\n";
    for(int i = 0; i < SIZE; i++){
        for(int j = 0; j < SIZE; j++){
            cout << dp[i][j] << "\t";
        }
        cout << "\n";
    }
    
    fin.close();
    fout.close();
    
    return 0;
}

Знаю, что задача похожа на перемножение матриц, но не могу учесть все варианты разбиения дороги.

Спасибо )

[xNut]

Сообщение от Feld

для железнодорожной сети на рисунке

где рисунок?

[Feld]

Screen Shot 2016-12-23 at 8.48.39 AM.jpg, пожалуйста

[Arigato]

xNut, это платная ветка форума, тут не обсуждают решение задачи, а ищут исполнителя за деньги. Готовы решить - свяжитесь с автором темы или оставьте свои координаты.