题解：P2135 方块消除
zzzyyyyhhhhh
·
·
题解
题解区没看到有这做法的，就发一篇题解吧。
首先区间最左（或最右）的颜色是可以放到组后消除并不影响答案的，所以我们钦定最后消除这个区间左端点，对于每个区间做一个背包，$g_{r,k}$ 表示最后一次消除的颜色中最后面的位置为 $r$ 且此颜色数量为 $k$ 的最大收益（不包括此颜色），最后取 $\max_{k,r}\{k^2+g_{r,k}\}$ 即为 $f_{l,r}$。
代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 60;
int n,co;
int f[N][N],g[N][1001];
int c[N],a[N];
inline void get(int l,int r)
{
int s=0,p=c[l],res=0;
g[l][a[l]]=0,s=a[l];
res=a[l]*a[l]+f[l+1][r];
for(int i=l+1;i<=r;i++)
{
if(c[i]!=p)continue;
s+=a[i];
for(int j=l;j<i-1;j++)
{
if(c[j]!=p)continue;
for(int e=a[i];e<=s;e++)
g[i][e]=max(g[i][e],g[j][e-a[i]]+f[j+1][i-1]),res=max(res,g[i][e]+e*e+f[i+1][r]);
}
}
s=a[l];
for(int i=l+1;i<=r;i++)
{
if(c[i]!=p)continue;
s+=a[i];
for(int j=l;j<i-1;j++)
{
if(c[j]!=p)continue;
for(int e=a[i];e<=s;e++)
g[i][e]=-1e9;
}
}
f[l][r]=res;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
memset(g,0xcf,sizeof g);
for(int i=1;i<=n;i++)cin>>c[i];
for(int i=1;i<=n;i++)cin>>a[i],f[i][i]=a[i]*a[i];
for(int len=2;len<=n;len++)
for(int l=1;l+len-1<=n;l++)
get(l,l+len-1);
cout<<f[1][n];
}
```