ABC015D 「高橋くんの苦悩」

#問題概要

• 制約付きナップザック(リンク)
• 荷物は$K$個までしか選べない
• $1 \le W \le 10^5, 1 \le N \le 50, 1 \le K \le N$

#最初に考えたこと

• 絶対dpでしょ
• 制約を無視して普通に考えて、最終的にその制約を満たすものを考えれば良い

#考察

• dp[i][j][w] := i番目までからj個選んだ時の幅合計w以下での最大の価値で良さそう

• 計算量は$O(WN^2)$なのでギリギリ余裕（？）

• 漸化式は

  • $w+weight[i] \le W$(つまり$i$番目を選べる時)では
    $dp[i+1][j+1][w+weight[i]] = max (dp[i][j][w] + value[i], dp[i][j][w+weight[i])$

  • 共通の操作として($i+1$番目までのものと$i$番目までのものを比較)
    $dp[i+1][j][w] = max (dp[i+1][j][w], dp[i][j][w])$

• 二つ目の漸化式がすんなり出てこなかった（デバッグしながら試行錯誤した）

• 一度式を立ててしまうと理屈づけるのは簡単だが、ひねり出すのに一苦労

#解答

answer.cpp

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define rep(n, i) Rep(0, n-1, i)

typedef long long ll;

const int MAX = 64;

int A[MAX], B[MAX], dp[MAX][MAX][10010];
//abc015d
void solve(void){
    //input
    int N, W, K;
    cin >> W >> N >> K;
    rep(N, i) scanf("%d %d\n", &A[i], &B[i]);

    //dp[i][j][w] := i番目まででj個選んだ時幅合計wでの最大の価値
    rep(N, i) Rep(0, N, j) Rep(0, W, w) {
        if (w+A[i] <= W) {
            dp[i+1][j+1][w+A[i]] = max(dp[i][j][w]+B[i], dp[i][j][w+A[i]]);
        }
        dp[i+1][j][w] = max(dp[i+1][j][w], dp[i][j][w]);
    }
    /*
    rep(K+1, k) {
        rep(W+1, w) printf("%d ", dp[N][k][w]);
        putchar('\n');
    }*/
    printf("%d\n", dp[N][K][W]);
}

int main(void){
  solve();
  return 0;
}

(リンク)

#最後に

• 時間かかりすぎた(2h以上はかけた)
• dpむずかちむずかち