题解：P2135 方块消除

前置说明：

$m$ 为颜色块数量， $n$ 为方块数量
令输入的第二行为数组 $a$ 表示颜色，第三行为数组 $c$ 表示颜色块大小

首先可以看出是一个区间 DP 题，但问题是直接设

f_{l,r}

会难以转移，因为难以体现区间内删掉一些方块后两边合并成一个新颜色块的过程。

注意到方块数量不会太多，考虑将其加入到状态中。类似于 CF150D 和 P5336 的思想，可以考察区间内最后剩下的状态。设

g_{l,r,x}

表示将区间

[l,r]

删到只剩大小为

x

的颜色块时，所能获取的最大收益。

但仅仅只是这样还不够，因为无法体现相同颜色块的合并。

于是考虑进一步设

g_{l,r,col,x}

表示将区间

[l,r]

删到只剩大小

x

，颜色为

col

的块。这样能得到一种转移，但是状态数是

O(m^3n)

的，算上转移的复杂度比较爆炸，考虑如何优化。

发现如果在一个区间

[l,r]

中，我们最后一次操作是删掉一个颜色为

col

的块。若这个块中在原区间里最右边的初始位置为

i

，那么实际上可以将操作分解为如下步骤：

先将区间 $[i+1,r]$ 删光；
再把区间 $[l,i]$ 删到只剩下一个颜色为 $col$ 的块。

这是因为区间

[i+1,r]

的删除操作不会影响最后剩下颜色块的结果，所以两部分可以分开算。更重要的是我们这时可以钦定区间中最后剩下的颜色与右端点相同，将状态进行优化。

设

g_{l,r,x}

表示将区间

[l,r]

删到只剩大小为

x

，颜色为

a_r

的颜色块的最大收益（这时钦定右端点对应颜色块必须保留），那么可以得到如下转移：

$g_{l,r,x}=\max_{i\in [l,i)} \{f_{l,i}+g_{i+1,r,x}\}$
若 $a_l=a_r$ ，有额外的转移 $g_{l,r,x}\gets g_{l+1,r,x-c_l}$
$f_{l,r}=\max(\max_{i\in [l,i)} \{f_{l,i}+f_{i+1,r}\},\max_x \{g_{l,r,x}+x^2\})$

状态数

O(m^2n)

，时间复杂度

O(m^3n)

，可以通过。

CPP

#include<bits/stdc++.h>
using namespace std;
#define N 55
int n,m,a[N],c[N],f[N][N],g[N][N][1010];
int main()
{
	memset(g,-1,sizeof(g));
	scanf("%d",&m);
	for(int i=1;i<=m;i++)scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)scanf("%d",&c[i]);
	for(int i=1;i<=m;i++)
		if(a[i]==a[n])c[n]+=c[i];
		else a[++n]=a[i],c[n]=c[i];
	for(int i=1;i<=n;i++)f[i][i]=c[i]*c[i],g[i][i][c[i]]=0;
	for(int d=1;d<n;d++)
	for(int l=1;l+d<=n;l++){
		int r=l+d;
		if(a[l]==a[r]){
			for(int x=c[l];x<=1000;x++)
				g[l][r][x]=max(g[l][r][x],g[l+1][r][x-c[l]]);
		}
		for(int i=l;i<r;i++)
		for(int x=1;x<=1000;x++)if(~g[i+1][r][x])
			g[l][r][x]=max(g[l][r][x],f[l][i]+g[i+1][r][x]);
		for(int x=1;x<=1000;x++)if(~g[l][r][x])
			f[l][r]=max(f[l][r],g[l][r][x]+x*x);
		for(int i=l;i<r;i++)
			f[l][r]=max(f[l][r],f[l][i]+f[i+1][r]);
	}
	printf("%d\n",f[1][n]);
}

题解：P2135 方块消除

文章操作

相关推荐

评论

题解：P2135 方块消除