专栏文章

题解：P8687 [蓝桥杯 2019 省 A] 糖果

jjiangyunuo
P8687题解参与者 4已保存评论 3

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@miori75m
此快照首次捕获于
2025/12/02 23:57
3 个月前
此快照最后确认于
2025/12/02 23:57
3 个月前
查看原文

本文记录：

2025 年 8 月 2 号过审
2025 年 8 月 9 号（本蒟蒻入谷二周年，给点面子吧），进行部分修改，改掉几处语言问题。

正文：

本蒟蒻在此之前没做过状态压缩动态规划，今日听教练讲了这题，所以特别写一篇题解。
本题意思大家都可以懂吧，所以今天我就直接从思路讲起。

第一思路：搜索

想法：

对于买糖这件事，我们一时可能找不到合适的做法，因而，我们可以从暴力打起，使用搜索算法。
思路的话就是一包一包糖果去搜，每搜一包糖果就会有两种可能，买或者不买，同时我们用一个 bool 型数组 visvis 来表示购买状态，即 visi=1vis_i=1 表示买第 ii 包糖果，visi=0vis_i=0 表示不买第 ii 包糖果。

代码：

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,k,t[105][25],ans=999; //ans 表示答案，初始化为 999，之后会记录最少购买的糖果包数。
bool vis[25],vis1[105][25];  //vis 数组见上文，vis1 数组是辅组数组，记录了对每一包糖果决策前 vis 的状态。
bool pd(){  //判断小明是否有 m 种口味的糖果。
	for(int i=1;i<=m;i++){
		if(!vis[i])return 0;
	}
	return 1;
}
void dfs(int x,int tot){  //x 表示当前决策的是第 x 包糖果，tot 表示到目前为止买的糖果包数。
	if(pd()){ans=min(ans,tot);return;}  //如果小明有 m 种口味的糖果，则记录答案。
	if(x>n)return;
	for(int i=1;i<=k;i++){   //见前文。
		vis1[x][t[x][i]]=vis[t[x][i]];
	}
	for(int i=1;i<=k;i++){   //见前文。
		vis[t[x][i]]=1;
	}
	dfs(x+1,tot+1);   //决定买下第 x 包糖果，接着向前搜索。
	for(int i=1;i<=k;i++){  //回溯。
		vis[t[x][i]]=vis1[x][t[x][i]];
	}
	dfs(x+1,tot);   //决定不买下第 x 包糖果，接着向前搜索。
}
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k;j++){
			cin>>t[i][j];
		}
	}
	dfs(1,0);
	if(ans!=999)cout<<ans<<endl;
	else cout<<-1<<endl;   //如果 ans 没变化，说明小明无法买到所有口味的糖果，因此输出 -1。
	return 0;
}
好消息：写出来了，没有逻辑错误。
坏消息：超时了。
测评记录。

第二思路：动态规划

确定算法：

暴力好是好，就是太慢了，容易超时，所以我们应该另辟蹊径。
我们不难想到动态规划。要知道，动态规划有两个特性，分别是可推导性与无后效性。
可以发现，本体两个特性都可以满足。
  1. 对于可推导性，我们知道了购买到哪几种口味的糖，我们就可以进一步向前推。就拿样例来说，一开始我们哪一种口味都没有，此时，我们的不需要购买任何一包糖，接着我们想知道购买到第一种口味的糖至少需要买几包糖，我们就可以推出来。已知没有购买到任何口味的糖不需要买任何一包糖，且第一包糖内包含了第一种口味的糖，所以我们想要购买到第一种口味的糖至少要买一包糖，可以证明，没有买更少包糖就可以获得第一种口味的糖的方法。
  2. 对于无后效性，我们可以知道，我们购买到哪几种口味的糖，与购买其他几种口味的糖无关，也就是说，这个结论求出后不会被后面的结论影响。还是拿样例来说，我们求出我们想要购买到第一种口味的糖就至少要买一包糖，之后这个结论是不可能改变的，毕竟购买别的口味的糖与购买第一种口味的糖没有什么关系。

设计状态：

既然确定了使用动态规划来完成这一题，我们就要开始设计状态。
可是，新的问题又随之出现了，按照传统的方法，我们设计的状态就会出问题。
如数字三角形，我们设计的状态是这样的：fi,jf_{i,j} 表示到达第 ii 行第 jj 列时我们获得的最大权值，这种方法就是通过位置来设计状态。再比如说采药，我们设计的状态是：fi,jf_{i,j} 表示前 ii 个物品在背包容量为 jj 的情况下能获得的最大价值，这种方法就是通过容量与物品来设计状态。再再比如说石子合并，我们设计的状态是：fi,jf_{i,j} 表示合并第 ii 个到第 jj 个石子所需的最小代价，这种方法就是通过区间来设计状态。
可以发现，前面举的几个例子状态都很简短，并且十分清晰，很好理解。但是，如果我们还是按着这种想法设计状态，那我们的状态就会很奇怪：一个 nn 维数组，第 ii 位是 11 表示购买第 ii 种口味的糖，反之亦然，这个数组的值表示在上述的情况下，所需要买的最少糖果包数。可问题又出现了，在数据大的情况下，这个数组就有很多维，这样麻烦不说，还特别容易错，对我们并不友好，所以我们需要换一种思路。
我们注意到，这个数组的每一维下标是 00 或者 11，大家有没有联想到什么？
作为 OIer，我们肯定都知道二进制（你可能会问，那刚入门的不知道怎么办，那我只能说，那你就不应该做这题，先把基础打好，毕竟连基础都没打扎实，学再多都没用），一个二进制串就是由 00 和 11 组成的，而且二进制和十进制是可以互相转换的。
照这样说，我们就可以把数组的这么多维看成一个二进制数，然后将这个数给转化为十进制，这样，就可以成功把压缩状态成一维。根据数据，我们确实可以实现这一点，m≤20m \le 20，所以，原本的数组最多最多只有二十维，看成二进制后最大为 1111111111111111111111111111111111111111，并且这个数转化为十进制后不超过 2×1062 \times 10^6，数组开的下，并且我们每一种情况都有它在数组中对应的结果，所以这种方法有效。
当然，在这样的情况下，我们还需要对糖果进行操作，我们已知前面设计的状态在二进制的情况下每一位都是表示一种口味的购买情况，所以我们可以给糖果制订新的编号。我们都知道，二进制数第 ii 位表示的数为 2i−12^{i-1} ，同样的，第 ii 种口味的糖果我们就给它编号为 2i−12^{i-1}。
举一个使用例子，55 的二进制是 101101，也就是二进制的 100+1100+1，化成十进制 4+14+1，也就是购买第 11 和第 33 种糖果。
补充一下，这种将状态从二进制的形式压缩成十进制的动态规划就是大名鼎鼎的状态压缩动态规划，并且这种动态规划的题目普遍数据比较小。

状态转移：

状态设计好了，接下来就是考虑转移了。
举个例子，我们已知 f5=1f_5=1（即获得第一种口味和第三种口味的糖需要买一包糖），又有一包糖，里面有第二种和第三种口味的糖，化成二进制，是这样的，状态：f101=1f_{101}=1，糖的二进制编号：110110，很显然，我们最终所获得的是第一到第三种口味的糖，二进制表示为 111111。由此可见，我们转移的状态并不是已知状态简单加上糖果编号得到的，而是根据它们的二进制位，如果已知状态或糖果编号在二进制的第 ii 位为 11 则新得到的状态第 ii 位也为 11，这点我们不难想到，毕竟一种口味的糖我们要想的是有还是没有，而不是有多少个。
可以发现，对于这样的情况，转移就变得很特别了，按照暴力思路，我们就会一位一位判断过去，但也太不方便了，有没有更简单的方法？
我可以告诉你，有的，兄弟有的。我们在这一题谈到了二进制与十进制，关于二进制，有一个知识点——位运算。位运算中的或运算就可以帮我们解决这个难题，或运算也是同样的原理，因此很好处理。
对于转移，一般有两种方法：
  1. 填表法，通过前面得出的结果，确定目前的结果。
  2. 刷表法，通过目前已知的结果，推出后面的结果。
显然，这里并不适合使用填表法，因为使用了或运算，我们难以知道前一个状态是什么，所以填表法不好用。但是刷表法好用，我们知道当前状态，也就可以知道买了一包新糖后的状态，相比填表法，会好写的多。
综上所述，我们可以推导出状态转移方程：s[i|t[j]]=min(s[i|t[j]],s[i]+1);（数组 tjt_j 表示第 jj 包糖果的编号。sis_i 表示当前已知状态）。

初始化问题：

对于表示状态的 ff 数组，我们从它的意义入手。我们，都知道，它表示的是买糖的最少包数，因此，我们可以一开始给它总体赋值一个超大的数，如 999999（话说也就最多 100100 包糖，这已经够了）。
接着，给 f0f_0 赋值为 00，毕竟你不买任何一包糖的时候你才会一种口味的糖都没有。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,a,k,t[105],s[2000000];
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k;j++){
			cin>>a;
			a=1<<(a-1);
			t[i]=t[i]|a;
		}
	}
	m=(1<<m)-1;
	for(int i=1;i<=m;i++){
		s[i]=999;
	}
	for(int i=0;i<=m;i++){
		for(int j=1;j<=n;j++){
			s[i|t[j]]=min(s[i|t[j]],s[i]+1);
		}
	}
	if(s[m]!=999)cout<<s[m]<<endl;
	else cout<<-1<<endl;
	return 0;
}
AC 记录。

评论

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

正在加载评论...