Advertisement
Josif_tepe

Untitled

Nov 24th, 2021
143
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. int n;
  5. int mat[21][3];
  6. int dp[21][4][4];
  7. int rek(int at, int prev, int last){
  8.     if(at == 0){
  9.         if(prev == last)return mat[0][prev];
  10.         return (1 << 30);
  11.     }
  12.     if(dp[at][prev][last] != -1){
  13.         return dp[at][prev][last];
  14.     }
  15.     int ret = (1 << 30);
  16.     if(prev == 0){
  17.         ret = min(ret, rek(at - 1, 1, last) + mat[at][0]);
  18.         ret = min(ret, rek(at - 1, 2, last) + mat[at][0]);
  19.     }
  20.     else if(prev == 1){
  21.         ret = min(ret, rek(at - 1, 0, last) + mat[at][1]);
  22.         ret = min(ret, rek(at - 1, 2, last) + mat[at][1]);
  23.     }
  24.     else if(prev == 2){
  25.         ret = min(ret, rek(at - 1, 0, last) + mat[at][2]);
  26.         ret = min(ret, rek(at - 1, 1, last) + mat[at][2]);
  27.     }
  28.     return dp[at][prev][last] = ret;
  29.      
  30. }
  31. int main(int argc, const char * argv[]) {
  32.     ios_base::sync_with_stdio(false);
  33.     cin >> n;
  34.     int a, b, c;
  35.     for(int i = 0; i < n; i ++){
  36.         cin >> a >> b >> c;
  37.         mat[i][0] = a;
  38.         mat[i][1] = b;
  39.         mat[i][2] = c;
  40.     }
  41.     memset(dp, -1, sizeof dp);
  42.     int ret = (1 << 30);
  43.     for(int i =0; i < 3; i ++){
  44.         for(int  j=0 ; j <3; j ++){
  45.             if(i != j)
  46.             ret = min(ret, rek(n - 1, i, j));
  47.         }
  48.     }
  49.     cout << ret << endl;
  50.     return 0;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement