自动搬运

查看原文

来自洛谷，原作者为

	FjswYuzu Rainybunny狂热粉丝!111111 | Last Goodbye

搬运于2025-08-24 22:14:28，当前版本为作者最后更新于2020-06-19 13:05:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

简单 dp。

考虑定义 $dp$ 数组，有关的只有当前任务，当前一级经验和二级经验。所以定义 $dp_{i,j,k}$ 为：当前选到了第 $i$ 个任务，一级经验和二级经验分别为 $j,k$。转移是非常明显的，只需要从没做这个任务的状态转移到下一个状态即可。

重要的是做任务的顺序不同，我们的答案也不同。因为一级溢出的经验会给二级，所以我们理性猜测一级能够得到的经验更多的任务放在后面。也就是把读入的任务以 $x$ 为关键字排序。

问题解决了！

注意卡空间要开滚动数组。不要开大可能会 T。一定要开 O2，太慢了。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=0x3f3f3f3f3f3f3f3f;
LL now;
#define Nxt (now^1)
struct task{
	LL x,t,y,r;
	bool operator < (task another) const {return x<another.x;}
}p[505];
LL n,s1,s2,dp[2][505][505];
int main(){
	scanf("%lld %lld %lld",&n,&s1,&s2);
	for(LL i=1;i<=n;++i)	scanf("%lld %lld %lld %lld",&p[i].x,&p[i].t,&p[i].y,&p[i].r);
	sort(p+1,p+1+n);
	memset(dp,0x3f,sizeof dp);//气气气这里不要用 127，memset 太慢了
	dp[0][0][0]=0;
	for(LL i=1;i<=n;++i)
	{
		memcpy(dp[Nxt],dp[now],sizeof dp[now]);//滚动数组将当前状态放上去。
		for(LL j=0;j<=s1;++j)
		{
			for(LL k=0;k<=s2;++k)
			{
				if(dp[now][j][k]!=INF)
				{
					if(j<s1)
					{
						LL level1=j+p[i].x;
						if(level1>s1)
						{
							LL overflow=level1-s1+k;
							overflow=min(overflow,s2);
							dp[Nxt][s1][overflow]=min(dp[Nxt][s1][overflow],dp[now][j][k]+p[i].t);
						}
						else	dp[Nxt][level1][k]=min(dp[Nxt][level1][k],dp[now][j][k]+p[i].t);
					}//将经验放在第一级，分情况讨论溢出到第二级和不溢出。
					LL level2=k+p[i].y;
					level2=min(level2,s2);
					dp[Nxt][j][level2]=min(dp[Nxt][j][level2],dp[now][j][k]+p[i].r); //放在第二级
				}
			}
		}
		now^=1;
	}
	printf("%lld",(dp[now][s1][s2]==INF || !dp[now][s1][s2])?-1:dp[now][s1][s2]);//能达到满级吗
	return 0;
}