洛谷题面

题目大意

小红说：“小明，你点菜吧。”小明看到菜单上有 \(N\) 道菜，每道菜的价格是 \(C_i\)。小明对每道菜的喜爱程度是 \(X_i\)，小红对每道菜的喜爱程度是 \(Y_i\)。（喜爱程度可能为负数）（小明：以我对她的了解，我给你的数据不会错的）

小明带了 \(V\) 元钱，他点的菜的总价格不能超过 \(V\)（小明：当然得我请客啦，显得我大方。）

小明希望让小红吃得开心，所以当然要让她的总喜爱程度尽量大。当然，小明也要考虑自己的感受，点的所有菜的总喜爱程度需要大于等于 \(0\)。（小明：要是我吃得不好，她看见我会难过的）

请你帮小明写一个程序，计算出他的总喜爱程度大于等于 \(0\) 的前提下，小红的喜爱程度的最大值。（小明：你的程序一定要靠谱啊，我得给她一个好印象）

题目分析

带有负权值的拓展 \(\rm 01\) 背包 老缝合怪了。

令 \(dp[i][j]\) 表示花费 \(i\) 元钱的情况下，小明的喜爱程度为 \(j\) 的时候，小红最高的喜爱程度。

当前状态，是由花费第 \(i\) 个菜之前转移过来的，也就是 \(dp[j-c[i]][k-x[i]]\)。

故状态转移方程为：\(dp[j][k]=\max\{dp[j-c[i]][k-x[i]]+y[i]\}\)。

注意到 \(k-x[i]\) 可能会小于 \(0\)，所以整体需要加上偏移量 \(\Delta=500\)（\(V\) 的范围）。

代码

const int R=500;

const int ma=1005;

int pri[ma],mr[ma],ms[ma];

int dp[ma][ma];
//dp[i][j]:花费 i 元钱的情况下,小明的喜爱程度为 j 的时候,小红最高的喜爱程度

int n,m;

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif

	n=read(),m=read();

	for(register int i=1;i<=n;i++)
	{
		pri[i]=read(),mr[i]=read(),ms[i]=read();
	}

	mst(dp,0xcf);

	dp[0][0+R]=0;

	for(register int i=1;i<=n;i++)
	{
		for(register int j=m;j>=pri[i];j--)
		{
			for(register int k=R;k>=-R;k--)
			{
				if(k-mr[i]<=R && k-mr[i]>=-R)
				{
					dp[j][k+R]=max(dp[j][k+R],dp[j-pri[i]][k-mr[i]+R]+ms[i]);
				}
			}
		}
	}

	int ans=-1;

	for(register int i=0;i<=m;i++)
	{
		for(register int j=0;j<=R;j++)
		{
			ans=max(ans,dp[i][j+R]);
		}
	}	

	printf("%d\n",ans);

	return 0;
}