题目链接
首先先预处理,把连续方块合一,变成 P2135 方块消除。 没错这题是双倍经验
设 \(dp(i, j, k)\) 为区间 \([i, j]\) 内后面与 \(a[j]\) 相同颜色的方块有 \(k\) 个,然后分两种情况考虑。
- 直接把 \([i, j-1]\) 裁掉,于是 \(dp(i, j, k)=dp(i, j-1, 0)+(b[j]+k)^2\)
- 在 \([i, j-1]\) 区间内找一段 \(p\) 使得 \(a[p]=a[j]\),于是 \(dp(i, j, k)=dp(i, p, k+b[j])+dp(p+1, j-1, 0)\)
可能解释得不太清,毕竟这道题我自己也还没完全吃透。
实现的话用记忆化搜索会方便点,直接放代码吧:
// Problem: UVA10559 方块消除 Blocks
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA10559
// Memory Limit: 0 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define mo
#define N 210
int n, m, i, j, k, t, p;
int a[N], b[N], c[N];
int dp[N][N][N];
int dfs(int l, int r, int k)
{
if(dp[l][r][k]!=-1) return dp[l][r][k];
int sum=b[r]+k;
if(l==r) return dp[l][r][k]=sum*sum;
int ans=dfs(l, r-1, 0)+sum*sum;
for(int i=l; i<r; ++i)
if(a[i]==a[r])
ans=max(ans, dfs(l, i, sum)+dfs(i+1, r-1, 0));
return dp[l][r][k]=ans;
}
signed main()
{
// freopen("tiaoshi.in", "r", stdin);
// freopen("tiaoshi.out", "w", stdout);
t=read();
for(p=1; p<=t; ++p)
{
m=read();
n=0;
memset(dp, -1, sizeof(dp));
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
for(int i=1; i<=m; ++i)
{
c[i]=read();
if(c[i]==c[i-1]) b[n]++;
else a[++n]=c[i], b[n]=1;
}
// for(i=1; i<=n; ++i) printf("%d %d\n", a[i], b[i]);
printf("Case %lld: %lld\n", p, dfs(1, n, 0));
// printf("%lld\n", dfs(1, n, 0));
}
return 0;
}