自动搬运

查看原文

来自洛谷，原作者为

	Gavin·Olivia **

搬运于2025-08-24 21:43:56，当前版本为作者最后更新于2018-10-31 15:36:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

魔鬼教练举行了一次连续三天的动规测试，这题是T2(一共31题）我再也不想打动规了（手动黄豆再见）

这题很明显是背包类动规，最容易想到的思路当然是像金明的预算方案一样做分组01背包，$f[i]$表示花费为$i$时奶牛的最大产出值。状态转移方程也很好推。然而，不用试也知道

$\huge{TLE!}$

经过观察我们可以很轻易地得到一个结论，每个游戏平台之间是互不影响的，那么我们就有了一个大胆的想法：可不可以把当前平台单独动规出来后与前面合并呢？所以就有了$g$数组，$g[j]$表示在已经买了当前平台$i$的前提下，在$1$~$i$平台共花费$j$元所能带来的最大产出,是个简单的01背包（我相信你们都会哒）。然后将$g$和$f$数组进行合并（$f[j]=max(f[j],g[j])$）。具体实现过程看代码。

#include<bits/stdc++.h>
 using namespace std;
 int i,j,k,n,v,p,gc,gp,pv;
 long long f[1000005],g[1000005];
 inline int read()
{
	int x=0,c; bool f=0;
	for(;(c=getchar())<'0'||c>'9';f|=c=='-');
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+c-48;
	return f?-x:x;
}
 int main()
{
	n=read(); v=read();
	for(i=1;i<=n;i++)
	{
		p=read(); gc=read();
		for(j=p;j<=v;j++) g[j]=f[j-p];
		for(j=1;j<=gc;j++)
		{
			gp=read(); pv=read();
			for(k=v-gp;k>=p;k--) g[k+gp]=max(g[k+gp],g[k]+pv);
		}
		for(j=p;j<=v;j++) f[j]=max(g[j],f[j]);
	}
	printf("%d",f[v]);
	return 0;
}