C - 駆引取引 みんなのプロコン 2018

C: 駆引取引 - 「みんなのプロコン 2018」 | AtCoder

制約
1≤N≤18
1≤xi,ci,vi≤10^15
与えられる入力は全て整数

解法
この記事を参考にしました　というかそのままです
駆引取引 [「みんなのプロコン 2018」C] - はまやんはまやんはまやん

n個を売った時に、買える商品の集合がmの時の最大価値dp[n][m]が知りたい。
それが分かれば、高橋くんは賞品を買うか買わないかの大きい方、青木くんは一番相手のスコアが悪くなるように販売を停止すればよい。

部分集合全部に対して料金の合計が超過しないか調べるのは大変なので、dp[n][m]でmを全て買えない時は0として
dp[n][m] = max(dp[n][mの部分集合)とすればいい
上はメビウス変換で出来る

  static int N;
    static long[] x, c, v;
    static long[][] dp, memo;

    public static long f(int n, int m) {
        if (memo[n][m] >= 0) return memo[n][m];
        if (n == N) return 0;
        //もう一つ売却するか
        long sold = LINF;
        for (int i = 0; i < N; i++) {
            if (bget(m, i)) {
                sold = Math.min(sold, f(n + 1, m - (1 << i)));
            }
        }
        //購入するか
        long buy = dp[n][m];
        return memo[n][m] = max(sold, buy);
    }

    public static void solve() {
        N = ni();
        x = nla(N);
        c = nla(N);
        v = nla(N);
        dp = new long[N + 1][1 << N];
        for (int n = 0; n < N + 1; n++) {
            long yen = 0;
            for (int i = 0; i < n; i++) {
                yen += x[i];
            }
            for (int m = 0; m < 1 << N; m++) {
                long co = 0;
                long va = 0;
                for (int i = 0; i < N; i++) {
                    if (bget(m, i)) {
                        co += c[i];
                        va += v[i];
                    }
                }
                if (co <= yen) dp[n][m] = va;
                else dp[n][m] = 0;
            }
            for (int i = 0; i < N; i++) {
                for (int m = 0; m < 1 << N; m++) {
                    if (bget(m, i)) {
                        dp[n][m] = Math.max(dp[n][m], dp[n][m ^ (1 << i)]);
                    }
                }
            }
        }
        memo = new long[N + 1][1 << N];
        fill(memo, -1);
        System.out.println(f(0, (1 << N) - 1));

    }