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

我们充分发扬人类智慧，注意到游戏可以无限取，所以要么取很少，要么几乎全取，所以只需要枚举取 $1 \sim 10$ 个和取最多的 10 个就可以过了。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,p[5010],w[5010];
ll f[5010],c[5010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(register int i=1;i<=n;i++){
		cin>>p[i]>>w[i]>>c[i];
		for(register int k=1;k<=10&&p[i]+w[i]*k<=m;k++){
			for(register int j=p[i]+w[i]*k;j<=m;j++){
				f[j]=max(f[j],f[j-p[i]-w[i]*k]+c[i]*k);
			}
		}
		for(register int k=(m-p[i])/w[i];k>=(m-p[i])/w[i]-10&&k>=1;k--)if(p[i]+w[i]*k<=m){
			for(register int j=p[i]+w[i]*k;j<=m;j++){
				f[j]=max(f[j],f[j-p[i]-w[i]*k]+c[i]*k);
			}
		}
	}
	cout<<f[m];
	return 0;
}

读题

我们来看一下题面，然后抓住一些关键信息。

1. 玩这款游戏之前需要花费 $p_i$ 的时间。
2. 一局游戏的时间为 $t_i$，得分为 $o_i$。
3. $n$ 种游戏，$m$ 分钟的时间。

对于上面这些十分轻易就能整理得出的信息，我们可以发现，这道题是一道与模板高度相似（不完全一样）的完全背包问题。

思路

那么对于题目的特殊条件，我们进行一个推导。

首先，我们设答案为 $f_{\max}$，也就是说，我们用一个 $f$ 数组存储答案，最后进行 $\max$。

由信息的第一点可知，我们对于每一个 $f_i$，都需要在递推（应该是叫递推吧）之前，进行一个 $f_i=f_{i-p_i}$，以此达到题目的要求。

然后第二点、第三点要求就非常容易理解了，这就是一个完全背包的板子，所以状态转移方程就不给了。

其实应该到这里就结束了，但是我们要进行一个正确的 dp，还要考虑一点，那就是 dp 的无后效性，这一点在我看来比前面的归纳总结都重要。

因此，我们需要用两个数组（下面结合代码分析这样的原因）$dp$ 和我们原来就有的 $f$。

大致的思路就讲到这里了，余下的事情在代码注释里看吧。

代码

#include<bits/stdc++.h>
#define int long long//十年OI一场空，不开long long见祖宗
using namespace std;
const int N=5e3+10;//个人习惯
int n,m;
int dp[N],f[N];
int p,t,o;
signed main(){
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		cin>>p>>t>>o;
		for (int j=m;j>=p;j--) dp[j]=f[j-p];//文章里面提到了，需要对当前的状态进行一个偏移，以此符合题目中p[i]的要求
		for (int j=t+p;j<=m;j++)//正常的完全背包板子
		{
			dp[j]=max(dp[j],dp[j-t]+o);//正常的完全背包板子
			f[j]=max(f[j],dp[j]);//更新f[i]的值
			//这里用dp和f来表示对于当前的时间来说，得分的Max值
			//用两个数组是因为f是最终答案，但是会受到每一次运算的影响
			//所以用dp作为一个暂时存储答案的数组，如果需要更新答案再对dp取Max
		}
	}
	int res=0;
	for (int i=1;i<=m;i++) res=max(res,f[i]);//我们需要对f整体取一个Max
	cout<<res;
	return 0;
}

需要强调的是，$o_i \le 10^9$，所以及其容易爆 long long。

完结撒花！！！