题目描述

解题思路

只考虑宝箱费用的时候：
这个题目在仔细分析之后可以大概知道是一个状态压缩dp的做法，dp[i][j]用来表示使用1-i个宝箱，并且状态为j(二进制压缩表示)的时候花的最少的钱，但是我们发现我们想用前一个状态更新当前状态的时候，我们不能确定前一个状态的j是哪一个。我们更新策略可以使用当前状态j来更新后一个状态，那么我们的i就整体向后面移动了一位。
相关理解
如果我们使用dfs解决：

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void dfs(int d,int state){
    if(d == n){
        //更新最后的价格
        res = Math.min(res,dp[d][(1<<m) - 1]);
    }
    
    //选择当前宝箱
    dp[d+1][state|s[d]] = dp[d][state] + cost[d];
    dfs(d+1,state|s[d]);
    dp[d+1][state] =  dp[d][state];
    //不选择当前宝箱
    dfs(d+1,state);
}

根据上面的伪代码我们可以理解，我们可以使用当前状态来更新后面状态的策略，其中我们更新的时候，被更新的状态一定是大于等于我们当前状态的，我们使用dp更新的时候，只要保证我们当前状态是被更新过或者被之前的所有状态经过就好了。
加上等级
我们可以根据等级来从小到大排序，在已有的dp循环加上最外层的一个等级循环，如果加上了这层循环一定会超时，我们可以进行优化，去掉外层循环，每次循环了一次i的时候我们就更新一次等级，这样是可以的。
注意：long a = 0x3f3f3f3f3f3f3f3fL需要这么赋值，如果是long a = 0x3f3f3f3f3f3f3f3f会被当int处理。

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.io.*;
import java.util.*;

class Main{
    public static int N = 110,M = 20,state = 1 << 20;
    public static int[] sx = new int[1<<20];
    public static Pair[] ps = new Pair[N];
    public static long[][] dp = new long[N][1<<m];
    public static Scanner sc = new Scanner(System.in);

    public static void main(String[] args){
        int n = sc.nextInt(),m1 = sc.nextInt(),b = sc.nextInt();
        for(int i = 1;i <= n;i++){
            int x = sc.nextInt();
            int k = sc.nextInt();
            int m = sc.nextInt();
            for(int j = 1;j <= m;j++){
                int u = sc.nextInt();
                sx[i] += (1 <<(u-1));
            }
            ps[i] = new Pair(x,k,m,sx[i]);
        }
        //根据登记排队
        Arrays.sort(ps,1,n+1,new Comparator<Pair>(){
            public int compare(Pair o1,Pair o2){
                return o1.k - o2.k;
            }
        });


        for(int i = 0;i <= n + 1;i++){
            Arrays.fill(dp[i],0x3f3f3f3f3f3f3f3fL);
            dp[i][0] = 0;
        }
        long res = 0x3f3f3f3f3f3f3f3fL;

        for(int i = 1;i <= n;i++){
            for(int j = 0;j < (1 << m1);j++){
                dp[i+1][j] = Math.min(dp[i+1][j],dp[i][j]);
                dp[i+1][j|ps[i].state] = Math.min(dp[i+1][j|ps[i].state],dp[i][j] + ps[i].x);
            }

            res = Math.min(dp[i+1][(1<<m1) - 1] + (long)b * ps[i].k,res);
        }
        if(res==0x3f3f3f3f3f3f3f3fL){
            System.out.println(-1);
            return;
        }
        System.out.println(res);


    }
    static class Pair{
        Integer x,k,m,state;
        public Pair(Integer x,Integer k,Integer m,Integer state){
            this.x= x;
            this.k = k;
            this.m = m;
            this.state = state;
        }
    }

}

优化代码

因为我们long[100][2e20] 的空间复杂度大概是 8B * 100 * 2e20 = 838,860,800B = 838MB会超时，需要优化一个维度。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.io.*;
import java.util.*;

class Main{
    public static int N = 110,M = 20,state = 1 << 20;
    public static int[] sx = new int[1<<20];
    public static Pair[] ps = new Pair[N];
    public static long[] dp = new long[1<<M];
    public static Scanner sc = new Scanner(System.in);

    public static void main(String[] args){
        int n = sc.nextInt(),m1 = sc.nextInt(),b = sc.nextInt();
        for(int i = 1;i <= n;i++){
            int x = sc.nextInt();
            int k = sc.nextInt();
            int m = sc.nextInt();
            for(int j = 1;j <= m;j++){
                int u = sc.nextInt();
                sx[i] += (1 <<(u-1));
            }
            ps[i] = new Pair(x,k,m,sx[i]);
        }
        //根据登记排队
        Arrays.sort(ps,1,n+1,new Comparator<Pair>(){
            public int compare(Pair o1,Pair o2){
                return o1.k - o2.k;
            }
        });


        Arrays.fill(dp,0x3f3f3f3f3f3f3f3fL);
        dp[0] = 0;
        long res = 0x3f3f3f3f3f3f3f3fL;

        for(int i = 1;i <= n;i++){
            for(int j = (1 << m1) - 1;j >= 0;j--)
                dp[j|ps[i].state] = Math.min(dp[j|ps[i].state],dp[j] + ps[i].x);
            res = Math.min(dp[(1<<m1) - 1] + (long)b * ps[i].k,res);
        }
        if(res==0x3f3f3f3f3f3f3f3fL){
            System.out.println(-1);
            return;
        }
        System.out.println(res);


    }
    static class Pair{
        Integer x,k,m,state;
        public Pair(Integer x,Integer k,Integer m,Integer state){
            this.x= x;
            this.k = k;
            this.m = m;
            this.state = state;
        }
    }

}