LightOJ 1422 Halloween Costumes 【 区间dp 】

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 
 8 int dp[505][505];
 9 int a[505];
10 int n;
11 
12 int main(){
13     int T;
14     int kase = 0;
15     scanf("%d",&T);
16     while(T--){
17         scanf("%d",&n);
18         for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
19         
20         for(int i = 1;i <= n;i++)
21          for(int j = i;j <= n;j++) dp[i][j] = 1;
22          
23          for(int i = n-1;i >= 1;i--){
24              for(int j = i;j <= n;j++){
25                  dp[i][j] = dp[i+1][j] + 1;
26                  for(int k = i+1;k <= j;k++){
27                      if(a[k] == a[i]) dp[i][j] = min(dp[i][j],dp[i+1][k-1] + dp[k][j]);
28                  //    printf("dp[%d][%d] = %d
",i,j,dp[i][j]);
29                  }
30              }
31          }
32          printf("Case %d: %d
",++kase,dp[1][n]);
33     }
34     return 0;
35 }