题目地址:http://poj.org/problem?id=2184
题目意思:
给你N个S,F
从中选择后,要使S+F的和最大,且S和F的和都不能为负
解题思路:
转化为当S去i时得到的F为dp[i]
最后就是求dp[i]+i的最大值
这就是一个01背包了
但是S和F均有负值
所以要有偏移量,除了这个问题
还要注意当s为负值时,背包容量就不是从后往前,而是从前往后
因为j-s会大于j,同一个j可能会加多次的f,想一想,为什么?
其实仔细想想也对,当s时正的时候,就是从后往前,当s变负,自然从前往后
下面上代码:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 100+10; const int maxv = maxn*1000; int dp[maxv+maxv]; int s[maxn],f[maxn]; int main() { int n; while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) scanf("%d%d",&s[i],&f[i]); for(int i=0;i<=maxv*2;i++) dp[i]=-9999999; dp[maxv]=0; for(int i=1;i<=n;i++) { if(s[i]>0) { for(int j=2*maxv;j>=s[i];j--) dp[j]=max(dp[j-s[i]]+f[i],dp[j]); } else { for(int j=0;j-s[i]<=2*maxv;j++) { dp[j]=max(dp[j-s[i]]+f[i],dp[j]); } } } int ans=0; for(int j=maxv;j<=2*maxv;j++) if(dp[j]>0) ans=max(ans,dp[j]+j-maxv); printf("%d\n",ans); } return 0; }