Halloween Costumes
题目链接：
http://lightoj.com/volume_showproblem.php?problem=1422
题意：
Gappu想要去参加一些party，他去每个party都要把特定编号的服装穿在外边，他可以穿上或者脱掉服装（脱掉的服装不能再穿一次，但是可以穿一件相同编号新的服装，最近穿的服装会套在之前穿的服装的外边），问Gappu最少需要准备多少套服装。
题解：
设dp[i][j]为区间 i 到 j （设len为区间长度，j=i+len）内最少需要的服装数， 那么可以发现dp[i][j]可以由两种方式得到：
① dp[i][j]=dp[i][j-1]+1
② 找到一个点k，k在区间[i][j-1]内且party k需要的服装和party j需要的服装相同，则此时 dp[i][j]=dp[i][k]+dp[k+1][j-1](之所以是k+1是为了保证不会将party k所需要的服装脱掉)
取①和②的较小值就好了，dp[1][n]为终点状态
代码
#include<stdio.h>
const int N=101;
int p[N],dp[N][N];
int mmin(int x,int y)
{
return x<y?x:y;
}
void solve()
{
int T,n,Case=0;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&p[i]);
dp[i][i]=1;
}
for(int len=1;len<n;++len)
for(int i=1;i+len<=n;++i)
{
int j=i+len;
dp[i][j]=dp[i][j-1]+1;
for(int k=i;k<=j-1;++k)
if(p[k]==p[j])
{
dp[i][j]=mmin(dp[i][j],dp[i][k]+dp[k+1][j-1]);
}
}
printf("Case %d: %d
",++Case,dp[1][n]);
}
}
int main()
{
solve();
return 0;
}