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

解题思路:

注意事项:

参考代码:
import java.util.Arrays;
import java.util.Scanner;

public class 糖果 {
   static int[] dp = new int[(1<<21)-1];
   public static void main(String[] args) {
//        System.out.println(Integer.toBinaryString((1<<21)-1));
       Scanner scanner = new Scanner(System.in);
       int N = scanner.nextInt();
       int M = scanner.nextInt();//口味数量
       int K = scanner.nextInt();
       Arrays.fill(dp,105);
//        System.out.println(Integer.toBinaryString((1<<M)-1));
//        System.out.println((1<<M)-1);
       int[] candies = new int[N + 2];
       for (int i = 1; i <= N; i++) {
           for (int j = 1; j <= K; j++) {
               candies[i]|=1<<(scanner.nextInt()-1);
           }
//            System.out.println(Integer.toBinaryString(candies[i]));
           dp[candies[i]]=1;
       }
            for(int j=1;j<=N;j++){
                for(int i=1;i<dp.length;i++){
                if(dp[i]!=105)
                    dp[i|candies[j]] = Math.min(dp[i]+1,dp[i|candies[j]]);
            }
        }
//            for(int i=1;i<=31;i++)
//                System.out.println(dp[i]);
            if(dp[(1<<M)-1]==105)
                System.out.println(-1);
            else
                System.out.println(dp[(1<<M)-1]);
   }
}