LightOJ 1422 Halloween Costumes

 1 //#pragma comment(linker, "/STACK:167772160")//手动扩栈~~~~hdu 用c++交
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<iostream>
 6 #include<queue>
 7 #include<stack>
 8 #include<cmath>
 9 #include<set>
10 #include<algorithm>
11 #include<vector>
12 // #include<malloc.h>
13 using namespace std;
14 #define clc(a,b) memset(a,b,sizeof(a))
15 #define LL long long
16 const int Inf = 0x3f3f3f3f;
17 const double eps = 1e-5;
18 const double pi = acos(-1);
19 // inline int r(){
20 //     int x=0,f=1;char ch=getchar();
21 //     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘) f=-1;ch=getchar();}
22 //     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
23 //     return x*f;
24 // }
25 
26 int a[110];
27 int dp[110][110];
28 
29 int main(){
30     int t;
31     int cas=1;
32     scanf("%d",&t);
33     while(t--){
34        clc(dp,0);
35        int n;
36        scanf("%d",&n);
37        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
38        
39        for(int i=1;i<=n;i++)
40         for(int j=i;j<=n;j++){
41             dp[i][j]=i-j+1;
42         }
43         for(int i=n;i>=1;i--){
44             for(int j=i;j<=n;j++){
45                 dp[i][j]=dp[i+1][j]+1;
46                 for(int k=i;k<=j;k++){
47                     if(a[k]==a[i])
48                     dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k][j]);
49                 }
50             }
51         }
52         printf("Case %d: %d\n",cas++,dp[1][n]);
53        } 
54     return 0;
55 }