题解：P11430 [COCI 2024/2025 #2] 游戏 / Igre

cy20110922 · 2024-12-23 13:57:49 · 题解

分析

先看一眼算法标签，哦是背包啊。再看一眼题目，既然可以多次游玩，那一定就是完全背包！

思路

本题跟完全背包不同的一点是他要先学习完游戏才能开始玩，所以只要把 dp 数组下标从 j 改为 t-j 就可以了。对于完全背包的做法 dp[j] 表示时间为 j 时所获得的最大分数。然后我们可以在创建一个数组 maxn 来实时保存最大值。最后便利一遍 maxn 找出最大值就可以了。

上代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[60000],c[60000],w[60000],t[60000],maxn[6000],sum=0;
signed main(){
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> t[i] >> w[i] >> c[i];
        for(int j=m;j>=t[i];j--){
            dp[j]=maxn[j-t[i]];
        }
        for(int j=w[i]+t[i];j<=m;j++){
            dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
            maxn[j]=max(maxn[j],dp[j]);
        }
    }
    for(int i=1;i<=m;i++){
        sum=max(sum,maxn[i]);
    }
    cout << sum;
    return 0;
}