Advertisement
Josif_tepe

Untitled

Nov 17th, 2021
209
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int dp[25][10][10];
  6. int n;
  7. int m[25][3];
  8. int rec(int i, int prev_color, int first_color) {
  9.     if(i == 0) {
  10.         if(prev_color == first_color) {
  11.             return m[0][prev_color];
  12.         }
  13.         return 100000;
  14.     }
  15.  
  16.     if(dp[i][prev_color][first_color] != -1) {
  17. //        return dp[i][prev_color][first_color];
  18.     }
  19.     int result = 100000;
  20.     for(int j = 0; j < 3; j++) {
  21.         if(prev_color != j) {
  22.             result = min(result, rec(i - 1, j, first_color) + m[i][j]);
  23.         }
  24.     }
  25.     dp[i][prev_color][first_color] = result;
  26.     return result;
  27. }
  28. int main()
  29. {
  30.     cin>>n;
  31.     for(int i=0; i<n; i++){
  32.         for(int j=0; j<3; j++){
  33.             cin>>m[i][j];
  34.         }
  35.     }
  36.     for(int i = 0; i < n; i++) {
  37.         for(int j = 0; j < 3; j++) {
  38.             for(int k = 0; k < 3; k++) {
  39.                 dp[i][j][k] = -1;
  40.             }
  41.         }
  42.     }
  43.     int result = 2e9;
  44.     for(int i = 0; i < 3; i++) {
  45.        
  46.         for(int j = 0; j < 3; j++) {
  47.             if(i != j) {
  48.                 result = min(result, rec(n - 1, i, j));
  49.             }
  50.         }
  51.     }
  52.     cout << result<< endl;
  53.     return 0;
  54. }
  55.  
  56.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement