题目及官方解题报告在这:here E题
#include<iostream> #include<cstdio> #include<cstring> #define maxn 1<<29 using namespace std; int main() { int t,m,n,num,aa,ca=1; int f[105][105],a[105]; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++)f[i][j]=maxn; } for(int i=1;i<=n;i++)f[i][i]=1; for(int j=2;j<=n;j++) { for(int i=j-1;i>=1;i--) { for(int k=i;k<j;k++) { if(a[i]==a[k+1])f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]-1); else f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]); } } } printf("Case %d: %d\n",ca++,f[1][n]); } return 0; }