Cow Exhibition [POJ2184] [DP] [背包的负数处理]

题意：

有很多羊，每只羊有一个幽默度和智商，要选出一些羊，智商加幽默度总和最大，其中智商总和和幽默度总和都不能是负数。

样例输入：

-5 7

8 -6

6 -3

2 1

-8 -5

样例输出：

分析：

这很像一个01背包题，但是有两个价值，却没有重量

我们就把其中一个看成重量，另一个看成价值

答案就是max(i+dp[i])

那如何保证数据大于0呢？

我们可以把价值总体向右移100000个单位，然后设原点O为100000

之后就可以进行dp了

转移方程仍是：dp[j]=dp[j-w[i]]+v[i];

但要注意，如果w[i]>=0要逆向循环,w[i]<0要顺向循环，确保是01背包而不是完全背包

最后计算结果时，从O向右枚举，保证了重量不为负数，dp[i]>=0，保证价值不为负数

再从中选max(i-O+dp[i])

代码：

 #include<set>

 #include<map>

 #include<queue>

 #include<stack>

 #include<cmath>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define RG register int

 #define rep(i,a,b)    for(RG i=a;i<=b;++i)

 #define per(i,a,b)    for(RG i=a;i>=b;--i)

 #define ll long long

 #define inf (1<<29)

 #define O 100000

 #define maxn 105

 #define maxm 200005

 using namespace std;

 int n;

 int dp[maxm],v[maxn],w[maxn];

 inline int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 int main()

 {

     n=read();

     rep(i,,n)    w[i]=read(),v[i]=read();

     //memset(dp,-63,sizeof(dp));

     dp[O]=;

     rep(i,,n)

     {

         if(v[i]>=)

             per(j,maxm-,v[i])

                 dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

         else

             rep(j,,maxm-+v[i])

                 dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

     }

     int ans=;

     rep(i,O,maxm-)

         if(dp[i]>=)

             ans=max(ans,dp[i]+i-O);

     cout<<ans;

     return ;

 }

巴特西

Cow Exhibition [POJ2184] [DP] [背包的负数处理]

最新文章

热门文章