LOJ-1422 万圣节服装

题意（大概翻译）：

小憨憨 参加圣诞节的一些派对，并且需要穿上对应派对的衣服，所以他需要多次换衣服，为了方便，他可以选择脱掉一些衣服或者穿上新衣服，比如说，他穿着 美队 的衣服，外面又穿着 钢铁侠 的衣服，当他要参加 美队 服装派对时，他可以选择脱掉 钢铁侠 的衣服（因为 钢铁侠 衣服的里面有 美队 的衣服），或者他可以在穿一件 美队 的衣服，小憨憨 是个爱干净的人，当他脱下 钢铁侠 的衣服后，如果需要再穿 钢铁侠 的衣服，他会选择再穿一件新的。（如果他先穿A衣服，又穿上B衣服，再穿一件C衣服，如果他想让最外面的衣服是A，他可以选择直接穿一件A，或者先把C脱掉，再把B脱掉）。

输入：

2

4

1 2 1 2

7

1 2 1 1 3 2 1

输出：

Case 1: 3

Case 2: 4

思路： 假设参加 n个派对， 存在i，j使得 1 <= i <= j <= n。啥都不考虑的情况下，那么从i~j就需要  j-i+1件衣服（第一个派对也要穿，即一个派对换一件衣服），根据这个情况来赋初值 dp[i][j] = j-i+1;

然后再考虑状态转移方程，即 从i~j个派对会不会有重复的派对k（衣服k）出现，即出现a[k] = a[i] (k > i)，即可以少一件衣服 ，那么得到递推方程为 ：

dp[i][j] = min(dp[i][j],  dp[i+1][k-1] + dp[k][j]);   

代码如下：

#include<cstdio>
#include<cstring>
#define min(a,b) ((a) < (b)? (a):(b))
const int maxn = 110;
int dp[maxn][maxn],a[maxn];
int n,t,cas;
int main(){
  scanf("%d",&t);
  for(cas =0 ;cas < t ; cas++){
    scanf("%d",&n);
    for(int i=1 ;i<=n ;i++)
    scanf("%d",&a[i]);
    for(int i=1 ;i<=n ;i++){    //n个聚会
      for(int j=i ;j<=n ;j++)    //从i到j
       dp[i][j] = j-i + 1;       //赋初值，啥都不干的情况下从i~j要j-i+1件衣服
    }
    for(int i=n-1 ;i>=1 ;i--)  //反着来，第一行的就是最小的
      for(int j=i ;j<=n ;j++){
        dp[i][j] = dp[i+1][j]+1;   //分割为两段，坐标为i单独一段，i+1~j为一段
        for(int k=i+1 ;k<=j ;k++) //i~j中是否存在这么一个k，a[k]=a[i]
         if(a[k] == a[i])
         dp[i][j] = min(dp[i][j], dp[k][j]+ dp[i+1][k-1]);   //递推方程
      }
      printf("Case %d: %d
",cas+1, dp[1][n]);
  }
  return 0;
}