Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstring>
- 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement