Advertisement
Josif_tepe

Untitled

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