1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| #include <iostream> #include <memory.h> using namespace std; int cost[1000][3], n, dp[1000][3], start; int dpf(int cur, int color) { if(dp[cur][color] != -1) return dp[cur][color]; if(cur == n - 1) return color == start ? 987654321 : cost[cur][color]; dp[cur][color] = 987654321; for(int i = 0; i < 3; i++) if(color != i) dp[cur][color] = min(dp[cur][color], dpf(cur+1, i)); return dp[cur][color] += cost[cur][color]; } int main() { scanf("%d",&n); for(int i = 0; i < n; i++) scanf("%d %d %d",&cost[i][0], &cost[i][1], &cost[i][2]); memset(dp, -1, sizeof(dp)); int ans = 987654321; for(; start < 3; ++start) { memset(dp, -1, sizeof(dp)); ans = min(ans, dpf(0, start)); } printf("%d\n",ans); }
|