分糖果问题c语言

#糖果店的老板一共有 M 种口味的糖果出售。为了方便描述，我们将 M 种口味编号 1 ∼ M。
小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而是 K 颗一包整包出售。
幸好糖果包装上注明了其中 K 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。
请编程实现以上内容，并计算：给定 N 包糖果，小明最少买几包，就可以品尝到所有口味的糖果。
【输入格式】
第一行包含三个整数 N、M 和 K。
接下来 N 行每行 K 这整数 T 1 ,T 2 ,··· ,T K ，代表一包糖果的口味。
【输出格式】
一个整数表示答案。如果小明无法品尝所有口味，输出 −1。
【样例输入】
6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2
试题I: 糖果 14
代码实现：
#include <bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);–i)
#define Mst(a,b) memset(a,(b),sizeof(a))
using namespace std;
int dp[1<<20]; //二进制状态压缩
int a[105];
int main()
{
//freopen(“in.txt”,“r”,stdin);
int m,n,k;
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
set v; //记录n包中所有糖果的种类数
memset(dp,0x3f,sizeof(int)*(1<<m)); //初始化
dp[0] = 0;
For(i,1,n)
{
int x = 0,y;
For(j,1,k)
{
scanf("%d",&y);
–y;
v.insert(y);
x |= (1<<y);
}
a[i] = x; //x的二进制形式第i位为1代表这个集合中有第i+1种糖果
dp[x] = 1;//这种状态只需要第i包糖果1包就可以达到
}
if((int)v.size()<m) //把n包唐都买了也吃不到m中糖果
{
printf("-1n");continue;
}
int ed = (1<<m)-1; //目标状态
For(i,1,n)
{
For(state,0,ed)
{
if(dp[state]>200) continue; //用已有的状态去更新加上第i包糖果后的状态
int to = a[i]|state;
dp[to] = min(dp[to],1+dp[state]);
}
}
printf("%dn",dp[ed]);
}

return 0;

}

最后

以上就是忧虑航空为你收集整理的分糖果问题c语言的全部内容，希望文章能够帮你解决分糖果问题c语言所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。