题目大意：有一串带颜色的方块，每次可以消掉颜色相同的一段，得到size^2的分数，问最多能得到多少分数。n≤200。
给这题状态跪下来。
显然的区间DP，但设f[i][j]是不够的。
考虑到之前做过的题，于是强制一下右端点，设成三维f[i][j][k]，k表示什么呢？
模模糊糊推到了记录和右端点相同的颜色，但还是不能计算，离正解最终还是差了一步。
记f[i][j][k]表示将区间[i,j]，j右边加上k个与区间右端点颜色相同的块清空的最大得分。
没错，区间DP设的状态跟外面的环境有关。
为什么要这样设？其实我不知道。
我之前是这么考虑的：记录内部最终有k个与右端点相同还没被消掉的，但是这个k完全没办法统计。
但是你记录外面的环境，就不用管，因为你处理的方式显然是记忆搜，不会有多余情况被搜到。
所以这题就是大胆设状态，脑洞清奇。
转移方程讨论一下，直接消/把最后一个的颜色跟前面一个颜色相同的一起处理，中间一节扣出来。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <complex>
#include <stack>
#define LL long long int
#define dob double
#define FILE "10559"
using namespace std; const int N = ;
int n,A[N],f[N][N][N]; inline int gi(){
int x=,res=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')res*=-;ch=getchar();}
while(ch<=''&&ch>='')x=x*+ch-,ch=getchar();
return x*res;
} inline int dfs(int i,int j,int k,register int r=){
if(f[i][j][k])return f[i][j][k];
for(r=j;r>=i && A[r]==A[j];--r);int p=(k+j-r)*(k+j-r);
if(r<i)return f[i][j][k]=p;f[i][j][k]=dfs(i,r,)+p;
for(register int l=r;l>=i;--l)
if(A[l]==A[j])
f[i][j][k]=max(f[i][j][k],dfs(i,l,k+j-r)+dfs(l+,r,));
return f[i][j][k];
} inline void solve(){
n=gi();memset(f,,sizeof(f));
for(int i=;i<=n;++i)A[i]=gi();
for(int i=;i<=n;++i)
for(int j=;j<n;++j)
f[i][i][j]=(j+)*(j+);
printf("%d\n",dfs(,n,));
} int main()
{
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
int Case=gi();
for(int t=;t<=Case;++t){
printf("Case %d: ",t);
solve();
}
fclose(stdin);fclose(stdout);
return ;
}
Blocks