StoneHaos

max_mod_7

Oct 23rd, 2021
675
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // ConsoleApplication1.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
  2. //
  3.  
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <vector>
  7.  
  8. using namespace std;
  9.  
  10. int dp[13];
  11. int matrix[13][13] = {
  12.     {0, 4, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  13.     {0, 0, 0, 6, 10, 8, 0, 0, 0, 0, 0, 0, 0},
  14.     {0, 0, 0, 0, 9, 11, 6, 0, 0, 0, 0, 0, 0},
  15.     {0, 0, 0, 0, 0, 0, 0, 9, 10, 0, 0, 0, 0},
  16.     {0, 0, 0, 0, 0, 0, 0, 11, 16, 0, 0, 0, 0},
  17.     {0, 0, 0, 0, 0, 0, 0, 0, 18, 7, 0, 0, 0},
  18.     {0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 0, 0, 0},
  19.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 8, 0},
  20.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 5, 0},
  21.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 11, 0},
  22.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7},
  23.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8},
  24.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  25. };
  26.  
  27. int main() {
  28.     for (int i = 0; i < 13; ++i) {
  29.         for (int j = 0; j < i; ++j)
  30.             if (matrix[j][i] != 0)
  31.                 dp[i] = max(dp[i], dp[j] + matrix[j][i]);
  32.     }
  33.     vector<int> way;
  34.  
  35.     for (int i = 12; i > 0;) {
  36.         for (int j = i - 1; j >= 0; --j) {
  37.             if (matrix[j][i] != 0 && (dp[j] + matrix[j][i]) == dp[i]) {
  38.                 way.push_back(j + 1);
  39.                 i = j;
  40.                 break;
  41.             }
  42.         }
  43.     }
  44.    
  45.     reverse(way.begin(), way.end());
  46.     for (int i = 0; i < way.size(); ++i) {
  47.         cout << way[i] << " -> ";
  48.     }
  49.     cout << "13\n" << dp[12] << "\n";
  50.     return 0;
  51. }
  52.  
RAW Paste Data