题解

DP[i][j]表示区间i~j所需的最少服装
1: 如果i这件衣服后面无法重复使用DP[i][j]=DP[i+1][j]+1

2: 如果i+1~j内有一个k与i一样,可以考虑在k这个位置重复利用i这件衣服即DP[i][j]=min(DP[i][j],DP[i][k-1]+DP[k+1][j])

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=107;
int dp[N][N],c[N],n,T;
int main(){
	scanf("%d",&T);
	rep(cnt,1,T){
		scanf("%d",&n);
		rep(i,1,n)scanf("%d",&c[i]);
		rep(i,1,n)dp[i][i]=1;
		rep(l,2,n)rep(i,1,n-l+1){
			int j=i+l-1;
			dp[i][j]=dp[i+1][j]+1;
			rep(k,i+1,j)if(c[k]==c[i])dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]);
		}
		printf("Case %d: %d\n",cnt,dp[1][n]);
	}
	return 0;
}