Time Lapse :12min 50sec

17404.cpp

c++

#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);
}