洛谷P2340 奶牛会展 题解

description:

贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果，所以贝西不希望出展奶牛的智商之和小于零，或情商之和小于零。满足这两个条件下，她希望出展奶牛的智商与情商之和越大越好，请帮助贝西求出这个最大值。

solution:

这道题可以想到用背包来做。

因为两个商是相对等价的，所以我们设一个为“价格”，一个为“价值”就行了。

这样就可以分别判断数组的下标和这个下标内值的正负来确认它是否可以更新答案。

但是下标有一个弊端就是不能为负

但这样也简单，只要把它们统一加上一个大值就行了。

注意这里也不能乱加，因为这个是要算入背包时间复杂度的，加上400*1000=400000就行了。

然后洛咕的数据好玄学，读入的数组开小了4倍还能A…

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int s[105],f[105];
int dp[900005];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&s[i],&f[i]);
	}
	memset(dp,-0x3f,sizeof(dp));
	dp[400000]=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i]>=0)
		for(int j=800000;j>=s[i];j--)
		{
			dp[j]=max(dp[j],dp[j-s[i]]+f[i]);
		}
		else
		{
			for(int j=0;j<=800000+s[i];j++)
			{
				dp[j]=max(dp[j],dp[j-s[i]]+f[i]);
			}
		}
	}
	int ans=0;
	for(int i=400000;i<=800000;i++)
	{
		if(dp[i]>=0)
		{
			ans=max(ans,dp[i]+i-400000);
		}
	}
	printf("%d\n",ans);
	return 0;
}