fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. #define MAX 1001
  4. using namespace std;
  5.  
  6. int N;
  7. int dp[MAX][4];
  8. int arr[MAX][4];
  9. int start;
  10.  
  11. int min(int x,int y){
  12.     return x < y ? x : y;
  13. }
  14.  
  15. int solve(int n,int k){
  16.     if(n==1){
  17.         for(int i = 1;i<=3;++i){
  18.             if(i == start)
  19.                 return dp[n][k] = arr[n][k];
  20.             else
  21.                 return dp[n][k] = 987654321;
  22.         }
  23.     }
  24.  
  25.  
  26.     int& ret = dp[n][k];
  27.     if(ret != -1)
  28.         return ret;
  29.  
  30.     if(k == 1)
  31.         return ret = arr[n][k] + min(solve(n-1,k+1),solve(n-1,k+2));
  32.     if(k==2)
  33.         return ret = arr[n][k] + min(solve(n-1,k+1),solve(n-1,k-1));
  34.     if(k==3)
  35.         return ret = arr[n][k] + min(solve(n-1,k-1),solve(n-1,k-2));
  36. }
  37.  
  38. int main(void){
  39.     cin>>N;
  40.     for(int i = 1;i<=N;++i){
  41.         for(int j = 1;j<=3;++j){
  42.             cin>>arr[i][j];
  43.         }
  44.  
  45.     }
  46.     int answer = 987654321;
  47.     for(int i = 1;i<=3;++i){
  48.         for(int j = 1;j<=3;++j){
  49.             if(i != j){
  50.                 answer =min(answer,solve(N,i));
  51.             }
  52.  
  53.         }
  54.     }
  55.     cout<<answer<<endl;
  56.     return 0;
  57. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
3
26 40 83
49 60 57
13 89 99
stdout
copy 
0
https://ideone.com/m0vFpT
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!