洛谷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;
} 
全部评论

相关推荐

05-29 20:34
门头沟学院 C++
KarlAllen:得做好直接春招的准备。学历差的话,一是面试要求会比学历好的严格不少,二是就算面试通过了也会被排序。总之暑期和秋招对于学历差的就是及其不友好
点赞 评论 收藏
分享
05-03 12:45
西南大学 Java
nsnzkv:你这项目写的内容太多了,说实话都是在给自己挖坑,就算简历过了,后面面试也难受
点赞 评论 收藏
分享
不想投了,不想面了,不想找了感觉自己像个小丑
用微笑面对困难:不是你去大学生就业平台看看啊,boss很多就是冲kpi的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务