初看这道题，想了想没头绪，感觉又要被虐了，按照《算法基础》郭老师的讲解，勉强接受了这个奇怪的状态转移方程，但是还是感觉很吃力，照着视频写了一遍之后，又去网上看了看别人的代码，我的天哪，比郭老师的简洁多了！然后自己独立写了一遍，终于感觉好多了。原本感觉无从下手的难题，最后自己能够独立写出来，这种感觉真好，不过，能写出来不代表下一道状态转移方程如此之怪的题目我也能写，还是要多学习，多思考~
最后想说的是，视频最后郭老师喝完水扔瓶子是真的骚
言归正传：
当遇到动归问题，我们的数学模型推不下去时，这道题其实给我们指明了方向：增加参数（维度），例如这道题就是三维动归
初看这道题首先想到的估计大家都差不多（大神除外），那就是用前n-1个数字序列的结果算出前n个数字序列的结果，很快发现这样做是不行的，于是陷入了泥浆...终于想到了，我们可以用i--j-1之间的数字序列的结果去算推i--j之间的数字序列的结果，试了试发现好像也不行，于是陷入了泥浆...
dp[L][R][K];
其中K代表R右侧和R颜色一样的那一小排方块的数量，这样子dp[1][n][0]就是最终解，转态转移方程就也能写出来了（别问我怎么想到的，我也没想到）：
1.最右侧单独消除，dp[L][R][K]=dp[L][R-1][0]+(len[R]+k)^2;
2.最右侧的，和区间段（L，R）中的某一块进行消除（要颜色一样能消除），假设iL< = p < R满足条件，则dp[L][R][k]=dp[L][p][k+len[R]]+dp[p+1][R-1][0]。
算出第一种的解，枚举所有第二种情况的解，取上面之中最大的结果即可，记得要记忆化搜索。
代码：
#include<iostream> #include<cstring> using namespace std; const int maxn=200+50; int color[maxn],len[maxn]; int ans[maxn][maxn][maxn]; int dp(int l,int r,int k){ int result,temp; if(ans[l][r][k]>0) return ans[l][r][k]; result=k+len[r]; result*=result; if(l==r){ ans[l][r][k]=result; return result; } result+=dp(l,r-1,0); for(int i=r-1;i>=l;i--){ if(color[i]!=color[r]) continue; temp=dp(l,i,len[r]+k)+dp(i+1,r-1,0); if(temp<result) continue; result=temp; } ans[l][r][k]=result; return result; } int main(){ // freopen("in.txt","r",stdin); int n,m,col,cnt; cin>>n; for(int i=0;i<n;i++){ cin>>m; cin>>color[1]; len[1]=1; cnt=1; for(int l=2;l<=m;l++){ cin>>col; if(col==color[cnt]) len[cnt]++; else{ ++cnt; color[cnt]=col; len[cnt]=1; } } memset(ans,0,sizeof(ans)); printf("Case %d: %d ",i+1,dp(1,cnt,0)); } }