2019年第十届蓝桥杯省赛-糖果（一维状压dp）

看到20的数据量很容易想到状压dp。

开1<<20大小的数组来记录状态，枚举n个糖包，将其放入不同状态中（类似01背包思想）

时间复杂度O(n*(2^20))。

import java.util.Arrays;

import java.util.Scanner;

public class Main {

    static Scanner sc = new Scanner(System.in);

    static int[][] a = new int[105][25];

    static int[] sta = new int[105];

    static int[] dp = new int[(1<<20)+5];

    public static void main(String[] args) {

        int n=sc.nextInt();

        int m=sc.nextInt();

        int k=sc.nextInt();

        Arrays.fill(dp, -1);

        dp[0]=0;

        for(int i=1;i<=n;i++){

            for(int j=1;j<=k;j++){

                a[i][j]=sc.nextInt();

                sta[i]|=1<<(a[i][j]-1);

            }

            dp[sta[i]]=1;

        }

        for(int i=1;i<=n;i++){

            for(int j=0;j<(1<<m);j++){

                if(dp[j]==-1) continue;

                if(dp[j|sta[i]]==-1||dp[j]+1<dp[j|sta[i]]){

                    dp[j|sta[i]]=dp[j]+1;

                }

            }

        }

        System.out.println(dp[(1<<m)-1]);

    }

}