[AtCoder] ABC 015 D – 高橋くんの苦悩

2020年9月23日2020年12月12日

問題

方針

ナップサック問題なので動的計画法で解きます。\( d(i, j, k) \) を スクリーンショット \( i \) まで見た時、\( j \) 枚貼り付けて幅が \( k \) であるときの重要度の合計の最大値とします。遷移式は、

\[ d(i + 1, j , k) = d(i, j, k)\]

と初期化したあとに、

\[ d(i + 1, j + 1, k + A_i) \leftarrow \max(d(i + 1, j + 1, k + A_i), d(i, j, k) + B_i)\]

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int main() {
    int W, N, K;
    cin >> W >> N >> K;
    int A[N], B[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
    }
    
    int d[N + 1][K + 1][W + 1]{};
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= K; j++) {
            for (int k = 0; k <= W; k++) {
                d[i + 1][j][k] = d[i][j][k];
            }
        }
        for (int j = 0; j < K; j++) {
            for (int k = 0; k < W; k++) {
                int w = k + A[i];
                if (w > W) break;
                chmax(d[i + 1][j + 1][w], d[i][j][k] + B[i]);
            }
        }
    }

    int best = 0;
    for (int i = 0; i <= K; i++) {
        for (int j = 0; j <= W; j++) {
            chmax(best, d[N][i][j]);
        }
    }
    cout << best << "\n";
    return 0;
}