题目大意
有n个带有颜色的方块，没消除一段长度为x的连续的相同颜色的方块可以得到x^2的分数，让你用一种最优的顺序消除所有方块使得得分最多。
分析
首先不难看出这是一个区间dp，于是我们考虑如何设计状态。我们设dp[i][j][k]表示考虑区间[i,j]，从j往后有k个方块和第j个颜色是相同的，这样的情况的最大得分。转移便是对于所有在[i,j]区间内且颜色等于j的j'的dp[i][j'][k+1]+dp[j'+1][j-1][0]的最大值，意为将[j'+1,j-1]这一部分先消除在消除剩下的，当然野村在一种情况就是把最后面k+1个方块现消除再消除剩下的。只要在这几种情况中取max就可以了。为了方便实现我们使用记忆化搜索。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
int dp[][][],col[];
inline void init(){
memset(dp,,sizeof(dp));
}
inline int work(int le,int ri,int k){
int i,j;
if(ri<le)return ;
if(dp[le][ri][k])return dp[le][ri][k];
dp[le][ri][k]=work(le,ri-,)+(k+)*(k+);
for(i=le;i<ri;i++)
if(col[i]==col[ri])
dp[le][ri][k]=max(dp[le][ri][k],work(le,i,k+)+work(i+,ri-,));
return dp[le][ri][k];
}
int main(){
int n,m,i,j,k,t;
scanf("%d",&t);
for(int _=;_<=t;_++){
init();
scanf("%d",&n);
for(i=;i<=n;i++)
scanf("%d",&col[i]);
printf("Case %d: %d\n",_,work(,n,));
}
return ;
}