动态规划（真毒瘤！）
变量声明：
$val[i]$:表示第$i$块颜色
$num[i]$:表示第$i$块颜色数量
$sum[i]$:表示$num$的前缀和
我们设计状态$f[l][r][k]$表示区间$(l,r)$中，后面还有$k$个与$val[r]$相同的数字
那么初始化如下：
$f[l][r][k]=f[l][r-1][0]+(num[r]+k)*(num[r]+k)$
状态转移如下：
$f[l][r][k]=max(f[l][r][k],f[l][j][num[r]+k]+f[j+1][r-1][0])$
完整代码：
#include<iostream>
#include<cstdio>
#define N 57
using namespace std;
int n;
int val[N],num[N],sum[N],f[N][N][N*N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&val[i]);
for(int i=1;i<=n;++i)
scanf("%d",&num[i]),sum[i]=sum[i-1]+num[i];
for(int i=0;i<=n;++i)
for(int l=1;l<=n;++l)
{
int r=l+i;
if(r>n)
break;
for(int k=0;k<=sum[n]-sum[r];++k)
f[l][r][k]=f[l][r-1][0]+(num[r]+k)*(num[r]+k);
for(int j=l;j<r;++j)
for(int k=0;k<=sum[n]-sum[r];++k)
if(val[j]==val[r])
f[l][r][k]=max(f[l][r][k],f[l][j][num[r]+k]+f[j+1][r-1][0]);
}
printf("%d",f[1][n][0]);
return 0;
}
原文：https://www.cnblogs.com/yexinqwq/p/10207363.html