最近数据结构学傻，先停一下，写会dp冷静一下。
LightOJ - 1422
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define pb(x) push_back(x) #define sca(x) scanf("%d",&x) #define inf 0x3f3f3f3f int a[105]; int dp[105][105]; int main() { int t; cin>>t; int cas=1; while(t--) { int n; cin>>n; for(int i=1;i<=n;i++)scanf("%d",&a[i]); memset(dp,0,sizeof(dp)); for(int len=1;len<=n;len++) { for(int i=1;i<=n;i++) { int j=i+len-1; if(j>n)break; dp[i][j]=dp[i][j-1]+1; for(int k=i;k<j;k++) { if(a[k]==a[j]) { dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j-1]); } } } } printf("Case %d: %d\n",cas++,dp[1][n]); } } /* 依旧是枚举长度，枚举区间起点终点。 对于新加入的一个点j 如果我们发现在这个区间里边有和j相等的衣服k 那我们就可以不用去管j了。 直接将[k+1，j-1]区间的衣服套上就行。 */ #include<ios
