专栏文章

题解：P5189 [COCI 2009/2010 #5] ZUMA

cchase_the_light
P5189题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min20o3d
此快照首次捕获于
2025/12/01 19:16
3 个月前
此快照最后确认于
2025/12/01 19:16
3 个月前
查看原文
十分有思维难度的一道区间动规题目。
一开始想到可以设计一个二维的状态，令 dpi,jdp_{i,j} 表示第 ii 位到第 jj 位的弹子被全部消除时需要放置的弹子的最少数量，然而很容易发现并不好转移，因为你并不好确定在 jj 这个位置之前有多少个数字与 cjc_j 相同，也就不好确定你究竟要增加多少个弹子。所以考虑增加一个状态。
通过惊人的注意力，我决定加入一个状态，令 dpi,j,xdp_{i,j,x} 表示在第 j+1j+1 到第 nn 位的与 cjc_j 颜色不同的弹子已经全部消除时，将第 ii 位到第 jj 位的弹子以及之后 xx 位与 cjc_j 颜色相同的弹子全部消除需要放置的弹子的最少数量。于是开始转移。
枚举区间长度与 ii，再枚举 xx，因为显然地，当 x≥kx \ge k 时，我不需要添加任何弹子，因此枚举毫无意义，所以只需枚举 [0,k−1][0,k-1] 中的所有数即可。进行初始化，此时 dpi,j,x=dpi,j−1,0+k−x−1dp_{i,j,x} = dp_{i,j-1,0} + k - x - 1，因为你要先消除第 ii 位到第 j−1j-1 位的所有弹子，所花费的代价也就是 dpi,j−1,0dp_{i,j-1,0}，然后再删除第 jj 位以及之后 xx 位与 cjc_j 颜色相同的弹子共计 x+1x+1 位弹子，所花费的代价也就是 k−x−1k - x - 1。当然，这样一般来说不会是最优的，因为在第 ii 位到第 j−1j-1 位的弹子中，可能存在颜色与 cjc_j 相同的弹子，因此枚举 [i,j−1][i,j-1] 中的所有 pp，如果 cj=cpc_j=c_p，那么可以令 dpi,j,x=min⁡(dpi,j,x,dpi,p,min⁡(x+1,k−1)+dpp+1,j−1,0)dp_{i,j,x} = \min(dp_{i,j,x},dp_{i,p,\min(x+1,k-1)}+dp_{p+1,j-1,0})，后面这串柿子的意思就是先去掉第 p+1p+1 位到第 j−1j-1 位的弹子，然后再去掉第 ii 位到第 pp 位的弹子及之后的第 jj 位以及我们所需要的之后的 xx 位，共计 x+1x+1 位。最后就会发现答案已经唾手可得，就是 dp1,n,0dp_{1,n,0}。 代码如下。时间复杂度 O(n3k)O(n^3k)。
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=105;
using ll=long long;
int dp[N][N][N],c[N],n,m;
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>c[i];
	for(int l=1;l<=n;l++){
		for(int i=1;i<=n-l+1;i++){
			int j=i+l-1;
			for(int x=0;x<m;x++){
				dp[i][j][x]=dp[i][j-1][0]+m-x-1;
				for(int k=i;k<j;k++){
					if(c[k]==c[j]) dp[i][j][x]=min(dp[i][j][x],dp[i][k][min(x+1,m-1)]+dp[k+1][j-1][0]);
				}
			}
		} 
	}
	cout<<dp[1][n][0];
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...