#include using namespace std; int main() { int n; cin >> n; vector> v(n, vector(3)); for(int i = 0; i < n; ++i){ cin >> v[i][0] >> v[i][1] >> v[i][2]; } vector>> dp1(n, vector>(3)); vector>> dp2(n, vector>(3)); for(int i = 0; i < 3; ++i){ dp1[0][i].first = v[0][i]; dp1[0][i].second = i; dp2[0][i].first = v[0][i]; dp2[0][i].second = i; } for(int i = 0; i < 3; ++i){ int left = (i+1)%3; int right = (i+2)%3; dp1[1][i].first = v[1][i] + dp1[0][left].first; dp1[1][i].second = dp1[0][left].second; dp2[1][i].first = v[1][i] + dp2[0][right].first; dp2[1][i].second = dp2[0][right].second; } for(int i = 2; i < n-1; ++i){ for(int j = 0; j < 3; ++j){ int l = (j+1)%3; int r = (j+2)%3; if(dp1[i-1][l].first < dp1[i-1][r].first){ dp1[i][j].first = v[i][j] + dp1[i-1][l].first; dp1[i][j].second = dp1[i-1][l].second; } else if(dp1[i-1][l].first > dp1[i-1][r].first){ dp1[i][j].first = v[i][j] + dp1[i-1][r].first; dp1[i][j].second = dp1[i-1][r].second; } else{ dp1[i][j].first = v[i][j] + dp1[i-1][r].first; if(dp1[i-1][r].second == dp1[i-1][l].second) dp1[i][j].second = dp1[i-1][r].second; else dp1[i][j].second = 3; } if(dp2[i-1][l].first < dp2[i-1][r].first){ dp2[i][j].first = v[i][j] + dp2[i-1][l].first; dp2[i][j].second = dp2[i-1][l].second; } else if(dp2[i-1][l].first > dp2[i-1][r].first){ dp2[i][j].first = v[i][j] + dp2[i-1][r].first; dp2[i][j].second = dp2[i-1][r].second; } else{ dp2[i][j].first = v[i][j] + dp2[i-1][r].first; if(dp2[i-1][r].second == dp2[i-1][l].second) dp2[i][j].second = dp2[i-1][r].second; else dp2[i][j].second = 3; } } } int small = 2e9; for(int i = 0; i < 3; ++i){ for(int j = 0; j < 3; ++j){ if(j == i || i == dp1[n-2][j].second) continue; if(small > v[n-1][i] + dp1[n-2][j].first) small = v[n-1][i] + dp1[n-2][j].first; } for(int j = 0; j < 3; ++j){ if(j == i || i == dp2[n-2][j].second) continue; if(small > v[n-1][i] + dp2[n-2][j].first) small = v[n-1][i] + dp2[n-2][j].first; } } cout << small; }

제출 #66311

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: