区间dp好难啊。。。。。。。。。。！
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int maxn=100+50; int dp[maxn][maxn]; int a[maxn]; int t,n; int main() { scanf("%d",&t); for(int zz=1;zz<=t;zz++) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) dp[i][i]=1; for(int l=2;l<=n;l++) { for(int i=1,j=l;j<=n;j++,i++) { if(a[i]==a[j]) dp[i][j]=dp[i][j-1];//如果第i天和第j天一样，那么就套在里面，即不在加衣服 else dp[i][j]=dp[i][j-1]+1;//否则就加衣服 for(int k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]); } } printf("Case %d: %d\n",zz,dp[1][n]); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/7374287.html
相关资源：数据结构—成绩单生成器