分析
状态和转移都比较奇妙的 DP 。
设 $dp_{i,j,k}$ 表示 $[i,j]$ 区间,后面还有 $k$ 个和 $j$ 颜色相同的方块的最大分数。
转移有两种:
- 拿掉 $j$ 和后面的 $k$ 块:$dp_{i,j-1,0}+(k+1)^2\to dp_{i,j,k}$ 。
- 设 $p$ 为 $[i,j)$ 中与 $j$ 颜色相同的块,那么可以拿掉 $[p+1,j-1]$ 中的块,把前后拼起来:$dp_{i,p,k+1}+dp_{p+1,j-1,0}\to dp_{i,j,k}$ 。
直接 DP 似乎不太好写,可以写记搜。
代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define clear(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long ll;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=200+10;
int n,a[N];
int o[N],pre[N];
ll dp[N][N][N];
inline ll dfs(int i,int j,int k) {
if (i>j) return 0;
if (dp[i][j][k]) return dp[i][j][k];
ll res=dfs(i,j-1,0)+(k+1)*(k+1);
for (re int l=pre[j];l>=i;l=pre[l])
res=max(res,dfs(i,l,k+1)+dfs(l+1,j-1,0));
return dp[i][j][k]=res;
}
int main() {
int T=read();
for (re int _=1;_<=T;++_) {
clear(o),clear(dp),clear(pre);
n=read();
for (re int i=1;i<=n;++i) a[i]=read();
for (re int i=1;i<=n;++i) pre[i]=o[a[i]],o[a[i]]=i;
printf("Case %d: %lld\n",_,dfs(1,n,0));
}
return 0;
}