[COCI 2009/2010 #5] ZUMA

本篇题解写得应该还挺详细。

思路

提供一种容易理解，时间复杂度为 $O(KN^3)$ 的算法（好像别的题解没有和我思路一样的）。

容易想到区间 DP，但依照传统分割转移，显然会漏掉区间左右端点一起消除的情况，而区间左右端点还可能一起与中间的某些同色点一同消除情况更优（见样例 3）。故我们还需要知道某个区间最后一次消除的点中，有多少是原序列中本来存在的点。不知道该信息怎么办？凉拌写进状态里。

设 $ans_{i,j}$ 表示区间 $[i,j]$ 全部消除最少需要插入几颗弹子。设 $dp_{i,j,p}$ 表示区间 $[i,j]$ 全部消除，其中区间的左右端点 $i$ 和 $j$ 最后一次一起消除，且最后一次消除（$i$ 和 $j$ 一起消除的操作）的点中有 $p$ 个原序列中本来存在的点（包含 $i$ 和 $j$），最少需要插入几颗弹子。显然，该状态只在 $c_{i}= c_{j}$ 时有意义。同时可以发现，对于所有 $p\ge K$ ，其最后一次消除的花费是相同的，我们并不需要关心最后一次具体是多少点一起消除。于是不妨将 $p\ge K$ 的状态合并到 $dp_{i,j,K}$，特别令 $dp_{i,j,K}$ 的最后一次消除的点数 $p\ge K$，故 $p\in [2,K]$。

考虑转移，$ans_{i,j}$ 的转移非常简单：

$$ans_{i,j} = \min ( \min_{x=i}^{j-1}\{ans_{i,x}+ans_{x+1,j}\},\min_{x=2}^{K}\{dp_{i,j,x}\})$$

当 $c_{i}=c_{j}$ 时，对于 $dp_{i,j,p}(p\in [3,K])$，我们会在区间 $[i+1,j-1]$ 中选取 $p-2$ 个同色点，我们可以枚举这些同色点的最后一个 $x$，要求 $c_{x}=c_{i}$，此时我们需要在 $[i,x]$ 中选 $p-1$ 个同色点。故有转移：

$$dp_{i,j,p} = \min_{x=i}^{j-1}\{\max (dp_{i,x,p-1}-(K-(p-1))+(K-p)+ans_{x+1,j-1},0)(c_{x}=c_{i})\} (p\in [3,K])$$

特别的，$dp_{i,j,2} = ans_{i+1,j-1}+K-2$。$dp_{i,j,K}$ 还可以等于 $$\min_{x=i}^{j-1}{dp_{i,x,K}+ans_{x+1,j-1}(c_{x}=c_{i})} $$，与上方的式子取 min 即可。

显然，时间复杂度为 $O(KN^3)$。

代码

挤进最优解第一页了。

#include<bits/stdc++.h>
using namespace std;
int n,k,c[105],dp[105][105][6],ans[105][105];
//这里的dp实际上没用dp[][][0]与dp[][][1],如果想优化空间可以减去
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&c[i]);
	for(int i=1;i<=n;i++)
	{
		ans[i][i]=k-1;
		for(int j=2;j<=k;j++)
			dp[i][i][j]=5000;
	}
	for(int l=2;l<=n;l++)
	{
		for(int i=1;i+l-1<=n;i++)
		{	
			int j=i+l-1;
			ans[i][j]=5000;
			for(int p=2;p<=k;p++) 
				dp[i][j][p]=5000;
			for(int x=i;x<=j-1;x++)
			{
				ans[i][j]=min(ans[i][j],ans[i][x]+ans[x+1][j]);
				if(c[i]==c[j])//这里其实不需要判a[i]=a[x],因为如果a[i]!=a[x],那么dp[i][x][]一定都为5000
				{
					for(int p=3;p<=k;p++)
						dp[i][j][p]=min(dp[i][j][p],max(dp[i][x][p-1]+ans[x+1][j-1]-1,0));
//初始化赋为大值,但不能太大,要不然上方的式子dp[i][x][p-1]+ans[x+1][j-1]-1可能爆int
					dp[i][j][k]=min(dp[i][j][k],dp[i][x][k]+ans[x+1][j-1]);
				}
			}
			if(c[i]==c[j])
			dp[i][j][2]=min(dp[i][j][2],ans[i+1][j-1]+k-2);
			for(int p=2;p<=k;p++)
				ans[i][j]=min(ans[i][j],dp[i][j][p]);
		}	
	}
	cout<<ans[1][n];
	return 0;
}