【ABC145】E - All-you-can-eat

atcoder.jp

解法

T - 0.5分後というのは、T-1分後と言い換えることができる。

T-1秒をこえて、料理を食べることができない場合、ただのナップザックDPで解くことができる。
具体的にDPの定義は次のようになる。
dp[i][j] ← i番目の料理まで食べるかどうか決め、最初の注文からj秒立っている時の満足度の最大値

ただしこの問題では、最後の料理だけはT-1秒を越えて食べることができる。
T-1秒を越えて食べることができるのは、最後の料理1つだけであるため、DPでどの料理を食べるかの探索だけを行い、一番食べる時間がかかる料理を最後に食べれば良い。

とりあえず昇順に並べておけば、最後に食べる料理を一番時間がかかる料理にできるため簡単に解くことができる。

実装

void solve(long long N, long long T, std::vector<long long> A, std::vector<long long> B){
    vector<pair<ll, ll>> vec;
    REP (i, N) {
        vec.push_back({A[i], B[i]});
    }
    // 昇順に並べておく
    ALL(sort, vec);

    // DPテーブル
    vector<vector<ll>> dp(N+1, vector<ll>(T+1, 0));

    REP (i, N) {
        REP (j, T) {
            // i番目の料理を食べる場合
            chmax(dp[i + 1][min(T, j + vec[i].first)], dp[i][j] + vec[i].second);
            // i番目の料理を食べない場合
            chmax(dp[i + 1][j], dp[i][j]);
        }
        // これを忘れない
        chmax(dp[i + 1][T], dp[i][T]);
    }

    // 集計して最大値を探す
    ll ans = 0;
    REP (i, T+1) chmax(ans, dp[N][i]);
    cout << ans << endl;
}```