题解：P2135 方块消除

题解区没看到有这做法的，就发一篇题解吧。

f_{l,r}

表示

l

到

r

全部消除所获得的最大收益，考虑如何处理一个区间

l,r

。

首先区间最左（或最右）的颜色是可以放到组后消除并不影响答案的，所以我们钦定最后消除这个区间左端点，对于每个区间做一个背包，

g_{r,k}

表示最后一次消除的颜色中最后面的位置为

r

且此颜色数量为

k

的最大收益（不包括此颜色），最后取

\max_{k,r}\{k^2+g_{r,k}\}

即为

f_{l,r}

。

代码。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 60;
int n,co;
int f[N][N],g[N][1001];
int c[N],a[N];
inline void get(int l,int r)
{
	int s=0,p=c[l],res=0;
	g[l][a[l]]=0,s=a[l];
	res=a[l]*a[l]+f[l+1][r];
	for(int i=l+1;i<=r;i++)
	{
		if(c[i]!=p)continue;
		s+=a[i];
		for(int j=l;j<i-1;j++)
		{
			if(c[j]!=p)continue;
			for(int e=a[i];e<=s;e++)
				g[i][e]=max(g[i][e],g[j][e-a[i]]+f[j+1][i-1]),res=max(res,g[i][e]+e*e+f[i+1][r]);
		}
	}
	s=a[l];
	for(int i=l+1;i<=r;i++)
	{
		if(c[i]!=p)continue;
		s+=a[i];
		for(int j=l;j<i-1;j++)
		{
			if(c[j]!=p)continue;
			for(int e=a[i];e<=s;e++)
				g[i][e]=-1e9;
		}
	}
	f[l][r]=res;
}
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	memset(g,0xcf,sizeof g);
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n;i++)cin>>a[i],f[i][i]=a[i]*a[i];
	for(int len=2;len<=n;len++)
		for(int l=1;l+len-1<=n;l++)
					get(l,l+len-1);
	cout<<f[1][n];
}

题解：P2135 方块消除

文章操作

相关推荐

评论

题解：P2135 方块消除