-
Notifications
You must be signed in to change notification settings - Fork 0
/
loj1047.cpp
66 lines (50 loc) · 1.07 KB
/
loj1047.cpp
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
using namespace std;
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define min(a,b) ((a<b)?(a):(b))
int dp[21][3],n;
int rgb[21][3];
int minimum(int a,int b,int c)
{
if(a<=b&&a<=c)
return a;
else if(b<=a&&b<=c)
return b;
else
return c;
}
int cheak(int f)
{
if(f<0)
return 2;
return f;
}
int solve(int i,int color)
{
if(i>n)
return 0;
if(dp[i][color]!=-1)
return dp[i][color];
return dp[i][color]=rgb[i][color]+min(solve(i+1,cheak(color-1)),solve(i+1,(color+1)%3));
}
int main()
{
int T,i,Case=1;
scanf("%d",&T);
while(T--)
{
memset(dp,-1,sizeof(dp));
//cin>>n;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&rgb[i][0],&rgb[i][1],&rgb[i][2]);
//cin>>rgb[i][0]>>rgb[i][1]>>rgb[i][2];
}
//cout<<"Case "<<Case++<<": "<<minimum(solve(1,0),solve(1,1),solve(1,2))<<endl;
printf("Case %d: %d\n",Case++,minimum(solve(1,0),solve(1,1),solve(1,2)));
}
return 0;
}