模拟赛3（第2题）

2.SMRTFUN

时间限制:3000MS
内存限制:256000KB

题目描述
“又肥又温顺，又大又笨，他们看起来那么傻，而且也不有趣……”

这些牛想要证明，他们是既有趣，又聪明的。为了这样做，Bessie组织了一个由牛组成的展览。她有N(1<=N<=100)头牛的情况：聪明程度Si(-1000<=Si<=1000)和有趣程度Fi（-1000<=Fi<=1000）。

Bessie必须选择一些牛来参展。牛的总的聪明值TS是所有参展牛的聪明值Si的和，总的有趣值TF是所有参展牛的有趣值Fi的和。Bessie希望能使TS和TF的和最大。但是，她仍然要求TF和TS都大于等于0，因为，如果其中一个小于0的话，对这个展出将是致命的。

所以，请帮助Bessie找到最大的TS和TF的和，而且这两个数都要非负。

输入
第一行，一个整数N，牛的个数。第2～N+1行，两个整数，依次是Si和Fi。

输出
仅一行，所求得的TS和TF的和

输入样例
5
-5 7
8 -6
6 -3
2 1
-8 -5

输出样例
8

样例说明
选择第1，3和4号牛。TS=-5+6+2=3，TF=7-3+1=5，所以，TS+TF=3+5=8。虽然，加上2号牛可以使总和变成10，但是，TF小于0，不符合要求。

说明
数据范围限制
1<=N<=100
(-1000<=Si<=1000)
(-1000<=Fi<=1000）

解题思路

将s值作为大小，t值作为价值
做01背包
设g[i]表示
s总值为i时，t的最大值
答案只需要从为非负数的i中找到最大的g[i]+i即可
总值可以从负数转移，关于s的正负需要分两种顺序转移

AC代码

#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
long long n,ans,s[100005],f[100005],dp[8000005];
int main()
{
   
	scanf("%lld",&n); 
	for(long long i=1;i<=n;i++)//输入
	 scanf("%lld%lld",&s[i],&f[i]);
	memset(dp,-0x3f,sizeof(dp));
	dp[400000]=0;
	//dp（核心）↓ 
	for(long long i=1;i<=n;i++)
	 if(s[i]>=0)//正数
	  for(long long j=800000;j>=s[i];j--)dp[j]=max(dp[j],dp[j-s[i]]+f[i]);//转移
	 else 
	  for(long long j=0;j<=800000+s[i];j++)dp[j]=max(dp[j],dp[j-s[i]]+f[i]);//转移
	//dp （核心）↑ 
	for(long long i=400000;i<=800000;i++)
	 if(dp[i]>=0)//正数
	  ans=max(ans,dp[i]+i-400000);
	printf("%lld",ans);
	return 0;
}

谢谢