lightoj1047

CODE

#include <iostream>
#include <cstring>
using namespace std;
int n;
int g[26][3];
int ncase;
int dp[25][5];
int main()
{
        int t;
        cin>> t;
        while(t--)
        {
                dp[0][0]=dp[0][2]=dp[0][1]=0;
                int n;
                cin >> n;
                for(int i=1;i<=n;i++)
                {
                        for(int j=0;j<3;j++)
                                cin >> g[i][j];
                }
                for(int i=1;i<=n;i++)
                {
                        dp[i][0]=min(dp[i-1][1],dp[i-1][2])+g[i][0];
                        dp[i][1]=min(dp[i-1][2],dp[i-1][0])+g[i][1];
                        dp[i][2]=min(dp[i-1][0],dp[i-1][1])+g[i][2];
                }
                int ans=min(dp[n][0],min(dp[n][1],dp[n][2]));
                cout <<"Case "<<++ncase<<": "<<ans<<endl;
        }
        return 0;
}