UVA10559 方块消除 Blocks 题解

设g[i][j][k]为消去区间[i,j]中的方块，只留下k个与a[i]颜色相同的方块的最大价值，f[i][j]为将[i,j]中所有方块消去的价值，转移自己yy一下即可。

为什么这样是对的？因为对于一段区间[i,j]一定存在一种最优方案使得i位置上的方块被最后一次消去，确定了最后一次消去的那k个方块的位置就可以把问题转换成若干个子区间上的子问题来解决。

复杂度是\(O(n^4)\)的，但是能过。

具体见代码：

#include<bits/stdc++.h>

using namespace std;

#define N 207

#define ll long long

int g[N][N][N],f[N][N];

int last[N][N],a[N];

int main()

{

    int n,t;

    scanf("%d",&t);

    for(int o=1;o<=t;o++)

    {

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	    scanf("%d",&a[i]);

	memset(g,-0x3f,sizeof(g));

	memset(f,0,sizeof(f));

	for( int i=1;i<=n;i++)

	{

	    memcpy(last[i],last[i-1],sizeof(last[i]));

	    last[i][a[i-1]]=i-1;

	}

	for(int i=n;i>=1;i--)

	    for(int j=i;j<=n;j++)

	    {

		f[i][j]=max((g[i][j][1]=f[i+1][j])+1,f[i][j]);

		for(int k=2;k<=n;k++)

		{

		    int p=a[j]==a[i]?j:last[j][a[i]];

		    while(p!=i&&g[i][p-1][k-1]!=g[0][0][0])

		    {

			g[i][j][k]=max(g[i][j][k],g[i][p-1][k-1]+f[p+1][j]);

			p=last[p][a[i]];

		    }

		    f[i][j]=max(f[i][j],g[i][j][k]+k*k);

		}

	    }

	printf("Case %d: %d\n",o,f[1][n]);

    }

    return 0;

}

巴特西

UVA10559 方块消除 Blocks 题解

最新文章

热门文章