CCCPaste

Untitled

#include 
#include 
using namespace std;
int n;
int mat[21][3];
int dp[21][4][4];
int rek(int at, int prev, int last){
    if(at == 0){
        if(prev == last)return mat[0][prev];
        return (1 << 30);
    }
    if(dp[at][prev][last] != -1){
        return dp[at][prev][last];
    }
    int ret = (1 << 30);
    if(prev == 0){
        ret = min(ret, rek(at - 1, 1, last) + mat[at][0]);
        ret = min(ret, rek(at - 1, 2, last) + mat[at][0]);
    }
    else if(prev == 1){
        ret = min(ret, rek(at - 1, 0, last) + mat[at][1]);
        ret = min(ret, rek(at - 1, 2, last) + mat[at][1]);
    }
    else if(prev == 2){
        ret = min(ret, rek(at - 1, 0, last) + mat[at][2]);
        ret = min(ret, rek(at - 1, 1, last) + mat[at][2]);
    }
    return dp[at][prev][last] = ret;
      
}
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin >> n;
    int a, b, c;
    for(int i = 0; i < n; i ++){
        cin >> a >> b >> c;
        mat[i][0] = a;
        mat[i][1] = b;
        mat[i][2] = c;
    }
    memset(dp, -1, sizeof dp);
    int ret = (1 << 30);
    for(int i =0; i < 3; i ++){
        for(int  j=0 ; j <3; j ++){
            if(i != j)
            ret = min(ret, rek(n - 1, i, j));
        }
    }
    cout << ret << endl;
    return 0;
}