博客

传送门


滚动dp

因为当前的状态只与dp【i-1】有关 我们没有必要保留前面所有的项的值 只需要保留对我们有用的即可

01背包 因为如果某一关卡直接跳过的话游戏就结束了 所以不能取max要给他一个初值后 再取最大值

#include<bits/stdc++.h>
using namespace std;
int dp[3][6100];
int a[6010],b[6110],c[6110],d[6101];
int main()
{
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	int i,j,k,m,n,t;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
//		memset(dp,0,sizeof(dp));
		for(i=1;i<=n;i++)
			cin>>a[i]>>b[i]>>c[i]>>d[i];
		for(i=0;i<=m;i++)
		dp[1][i]=dp[0][i]=-1;
		dp[0][0]=0;
		long long ans=0;
		for(i=1;i<=n;i++)
		{
			for(j=0;j<=m;j++)
			{
				k=-1;
				if(j>=a[i]&&dp[i-1&1][j-a[i]]>=0)
				k=dp[i-1&1][j-a[i]]+b[i];
				if(j>=c[i]&&dp[i-1&1][j-c[i]]>=0)
				k=max(k,dp[i-1&1][j-c[i]]+d[i]);
				dp[i&1][j]=k;
				if(dp[i&1][j]>ans)
				ans=dp[i&1][j];
			}
		}
		cout<<ans<<endl;
	}
}