原题链接：蓝桥杯2019年第十届省赛真题-糖果
解题思路:状态压缩将每种状态用二进制的形式表示
例如第一包糖果：1 1 2
可以表示为：00011
表示第一种和第二种口味都有
而11111表示五种口味都有
dp[j]:表示当j状态的时，最少需要几包糖果构成
状态转移方程：
if(dp[j]==0){
continue;
}else{
if(dp[j | mzhuangtai[i]]==0){
dp[j | mzhuangtai[i]]=dp[j]+dp[mzhuangtai[i]];
}else{
dp[j | mzhuangtai[i]]=Math.min(dp[j | mzhuangtai[i]], dp[j]+dp[mzhuangtai[i]]);
}
}
模拟一下，一个一个进行或运算，最后找到最佳值
参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(),m=sc.nextInt(),k=sc.nextInt(); //n包糖果，m种类，每包k个糖 int[] dp=new int[(1<<m)-1+1]; //dp[i]=value: i状态口味需要value包糖果构成 int[] mzhuangtai=new int[n]; for(int i=0;i<n;i++){ for(int j=0;j<k;j++){ int weidao=sc.nextInt(); mzhuangtai[i] |= 1<<weidao-1; //按位或运算符优先级 低于 加减运输符 } dp[mzhuangtai[i]]=1; } for(int i=0;i<n;i++){ for(int j=0;j<(1<<m);j++){ if(dp[j]==0){ continue; }else{ if(dp[j | mzhuangtai[i]]==0){ dp[j | mzhuangtai[i]]=dp[j]+dp[mzhuangtai[i]]; }else{ dp[j | mzhuangtai[i]]=Math.min(dp[j | mzhuangtai[i]], dp[j]+dp[mzhuangtai[i]]); } } } } System.out.println(dp[(1<<m)-1]==0?-1:dp[(1<<m)-1]); }} |
8 分
4 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复