max_mod_7

// ConsoleApplication1.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int dp[13];
int matrix[13][13] = {
    {0, 4, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 6, 10, 8, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 9, 11, 6, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 9, 10, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 11, 16, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 18, 7, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 8, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 5, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 11, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
};

int main() {
    for (int i = 0; i < 13; ++i) {
        for (int j = 0; j < i; ++j)
            if (matrix[j][i] != 0)
                dp[i] = max(dp[i], dp[j] + matrix[j][i]);
    }
    vector<int> way;

    for (int i = 12; i > 0;) {
        for (int j = i - 1; j >= 0; --j) {
            if (matrix[j][i] != 0 && (dp[j] + matrix[j][i]) == dp[i]) {
                way.push_back(j + 1);
                i = j;
                break;
            }
        }
    }

    reverse(way.begin(), way.end());
    for (int i = 0; i < way.size(); ++i) {
        cout << way[i] << " -> ";
    }
    cout << "13\n" << dp[12] << "\n";
    return 0;
}