题解 2302: 蓝桥杯2019年第十届省赛真题-糖果-状态压缩dp思想

解题思路:状态压缩将每种状态用二进制的形式表示

例如第一包糖果：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]]);
        }

}


模拟一下，一个一个进行或运算，最后找到最佳值

参考代码:

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]);
    }
}