UVa

Luogu

分析

状态和转移都比较奇妙的 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;
}