题目大意:
输入 n
接下来 n 行 每行输入 a b
输出 n 行中 a+b 总和最大的同时满足 所有 a 总和 >=0 所有 b 总和 >=0 的值
负数的 01 背包应该反过来
w[i] 为正数时 需要从大往小推 即往 0 推
w[i] 为负数时 同样应该往 0 推 即与正数反过来
- #include <bits/stdc++.h>
- #define INF 0x3f3f3f3f
- using namespace std;
- int s[105],f[105],dp[1000*100*2+5];
- int main()
- {
- int n;
- while(~scanf("%d",&n))
- {
- int mid=n*1000;
- int ed=mid*2+5;
- for(int i=0;i<n;i++)
- scanf("%d%d",&s[i],&f[i]);
- memset(dp, -INF, sizeof(dp));
- dp[mid]=0;
- for(int i=0;i<n;i++)
- {
- if(s[i]>=0)
- {
- for(int j=ed;j>=s[i];j--)
- dp[j]=max(dp[j],dp[j-s[i]]+f[i]);
- }
- else
- {
- for(int j=s[i];j-s[i]<ed;j++)
- dp[j]=max(dp[j],dp[j-s[i]]+f[i]);
- }
- }
- int ans=-ed;
- for(int i=mid;i<ed;i++)
- if(dp[i]>=0) ans=max(ans,i-mid+dp[i]);
- printf("%d\n",ans);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2613408.html