糖果-蓝桥杯19省赛

简介: 糖果-蓝桥杯19省赛

问题描述


糖果店的老板一共有 M 种口味的糖果出售。为了方便描述,我们将 M 种口味编号 1 ∼ M。

小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果,而是 K 颗一包整包出售。

幸好糖果包装上注明了其中 K 颗糖果的口味,所以小明可以在买之前就知道每包内的糖果口味。

给定 N 包糖果,请你计算小明最少买几包,就可以品尝到所有口味的糖果。

【输入格式】

第一行包含三个整数 N、M 和 K。接下来 N 行,每行 K 个整数 T1, T2, · · · , TK,代表一包糖果的口味。

【输出格式】

一个整数表示答案。如果小明无法品尝所有口味,输出 −1。

【样例输入】


1. 6 5 3  
2. 1 1 2  
3. 1 2 3  
4. 1 1 3  
5. 2 3 5  
6. 5 4 2  
7. 5 1 2

【样例输出】

2

【评测用例规模与约定】

对于 30% 的评测用例,1 ≤ N ≤ 20 。

对于所有评测样例,1 ≤ N ≤ 100,1 ≤ M ≤ 20,1 ≤ K ≤ 20,1 ≤ Ti ≤ M 。


思路


我们设口味组合为i,我们的i用状态压缩的方法,使用二进制数表达,如2,3,5这组数据,我们用二进制数10110表示。

我们定义状态dp[i],表示得到口味i所需的最少糖果包的数量

状态转移方程:我们先计算出当前这包糖果中的种类的二进制表达,然后遍历所有口味,用或运算求得了新的口味组合newcase。

如果dp[newcase]==-1的话,说明这种组合之前没有实现过,那么我们实现它所需要的包数就是当前组合的包数+1,即dp[i]+1;如果dp[newcase]!=-1,那么我们判断dp[newcase]是否大于dp[i]+1,因为此时dp[newcase]代表着之前实现newcase组合的包数,而dp[i]+1是我们现在这种取包的方法取的包数,我们选择二者中小的那个。


代码python


1. N,M,K = map(int,input().split())
2. tot=1<<M
3. dp = [-1 for _ in range(1<<20)]
4. dp[0]=0
5. kw=[]
6. 
7. for _ in range(N):
8.     kw.append([int(i) for i in input().split()])
9. 
10. for c in kw:
11.     tmp=0
12. for x in c:
13.         tmp |=1<<x-1
14. for i in range(tot):
15. if dp[i]==-1:
16. continue
17.         newcase = i|tmp
18. if dp[newcase]==-1 or dp[newcase]>dp[i]+1:
19.             dp[newcase]=dp[i]+1
20. print(dp[tot-1])

代码c++


1. #include<bits/stdc++.h>
2. using namespace std;
3. int dp[1<<20]; //dp[v]:得到口味为v时需要的最少糖果包数量
4. int kw[100];   //kw[i]:第i包糖果的口味
5. 
6. int main() {
7.     int n,m,k; 
8.     cin>>n>>m>>k;
9.     int tot = (1<<m)-1;  //tot:二进制是m个1,表示所有m种口味
10.     memset(dp, -1, sizeof dp);
11. 
12. for (int i=0; i<n; i++){
13.         int tmp=0;
14. for (int j=0; j<k; j++){  //输入一包糖果中k种口味
15.             int x;  cin>>x;
16.             tmp|=(1<<x-1);  //状态压缩:把这包糖果种k种口味用tmp表示
17.         }
18.         kw[i]=tmp;   //kw[i]:第i包糖果的口味
19.         dp[tmp]=1;   //dp[v]:得到口味为v时需要的最少糖果包数量
20.     }
21. for (int i=0; i<=tot; i++)  //遍历所有口味组合
22. if (dp[i]!=-1)          //已存在得到口味i的最少糖果包数量
23. for (int j=0; j<n; j++)  {  //检查给定的n包糖果
24.                 int tmp = kw[j];
25. if (dp[i|tmp]==-1 || dp[i|tmp] > dp[i]+1 ) //状态转移
26.                     dp[i|tmp] = dp[i]+1;
27.             }
28.     cout << dp[tot];  //得到所有口味tot的最少糖果包数量
29. return 0;
30. }
目录
相关文章
|
12月前
|
算法
蓝桥杯算法竞赛第一周题型总结
蓝桥杯算法竞赛第一周题型总结
73 0
|
移动开发 Shell
蓝桥杯:2020 国赛 例题:天干地支
蓝桥杯:2020 国赛 例题:天干地支
73 0
|
21天前
lanqiao OJ 182 小朋友崇拜圈
lanqiao OJ 182 小朋友崇拜圈
27 2
|
27天前
|
算法
AcWing 1355. 母亲的牛奶(每日一题)
AcWing 1355. 母亲的牛奶(每日一题)
|
6月前
|
测试技术
题目1444:蓝桥杯2014年第五届真题斐波那契
题目1444:蓝桥杯2014年第五届真题斐波那契
53 0
|
算法 测试技术
蓝桥杯2022年第十三届决赛真题-卡牌——二分法
蓝桥杯2022年第十三届决赛真题-卡牌——二分法
123 0
|
测试技术
蓝桥杯2021年第十二届省赛真题-砝码称重(动态规划)
蓝桥杯2021年第十二届省赛真题-砝码称重(动态规划)
题目 2664: 蓝桥杯2022年第十三届省赛真题-求和
题目 2664: 蓝桥杯2022年第十三届省赛真题-求和
|
测试技术
题目2674:蓝桥杯2022年第十三届省赛真题-求阶乘
题目2674:蓝桥杯2022年第十三届省赛真题-求阶乘
【蓝桥杯基础题】2017年省赛—九宫幻方
【蓝桥杯基础题】2017年省赛—九宫幻方
【蓝桥杯基础题】2017年省赛—九宫幻方