Kinugoshi's Break Fast

2 secs 1024 MB

種類ごとの満足度を前計算しておくことを考えます。
満足度の計算式が料理のおいしさ $\times$ ジャンルの好きさなので、
他に何の料理を食べたとしても変わらないため前計算が可能です。
すると、満足度を $value$ 、腹持ちを $weight$ としたナップサックDPになるため、この問題を $O(NM)$ で解くことができました。
オーバーフローに注意しましょう。

writer解

xxxxxxxxxx
 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
​
int main() {
    int N, M, A, B, C;
    cin >> N >> M >> A >> B >> C;
    vector<pair<ll, ll>> food(N);
    vector<vector<ll>> dp(N + 1, vector<ll>(M + 1));
    for (int i = 0; i < N; i++) {
        ll x, y, z;
        cin >> x >> y >> z;
        food[i].first = z;
        if (x == 1) food[i].second = y * A;
        if (x == 2) food[i].second = y * B;
        if (x == 3) food[i].second = y * C;
    }
    dp[0][0] = 0;
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M + 1; j++) {
            if (j >= food[i].first) dp[i + 1][j] = max(dp[i][j - food[i].first] + food[i].second, dp[i][j]);
            else dp[i + 1][j] = dp[i][j];
        }
    }
    cout << dp[N][M] << endl;
}