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

· · 题解

分析

经观察,因为每个游戏可以重复学习和游玩,所以可以断定此题为完全背包问题

思路

我们可以用数组 a 来表示每个游戏的学习时间,用数组 b 来表示每个游戏的游玩时间,用数组 c 来表示每个游戏的价值,因此,我们可以用一个 w 数组来表示 ab 的和,简单点来讲就是背包模板里面的花费,用循环变量 i 来表示游戏的编号,用循环变量 j 来枚举价值,用 dp _ {j,i} 来递推,再利用数组 k 来维护 dp 数组的最大性,然后即可推出递推式:

dp _ {j,i}=k _ {j-a_i}

dp _ {j,i}=\max(dp _ {j,i},dp _ {j-b _ i,i}+c _ i) 最后输出 $k _ m$ 即可。 **代码** ```cpp #include<bits/stdc++.h> using namespace std; long long a[5001],b[5001],c[5001],k[5001],dp[5001][5001],w[5001]; int main() { long long n,m; cin>>n>>m; for(long long i=1;i<=n;i++) { cin>>a[i]>>b[i]>>c[i]; w[i]=a[i]+b[i]; } for(long long i=1;i<=n;i++) { for(long long j=m;j>=a[i];j--) { dp[j][i]=k[j-a[i]]; } for(long long j=w[i];j<=m;j++) { dp[j][i]=max(dp[j][i],dp[j-b[i]][i]+c[i]); k[j]=max(k[j],dp[j][i]); } } cout<<k[m]; return 0; } ```