poj(2184)——Cow Exhibition（01背包变形）
分类：动态规划学习
动态规划01背包变形
其实我想说这道题我觉得我自己并没有深刻的理解。但是今天做了一下，先把现在的想法记录下来 。
题目的大致意思是：
有N头牛，每头牛都有一个s值代表智商值，f值代表它的幽默值。
然后问你智商值和幽默值的总和值最大是多少，其中必须保证智商值的和与幽默值的和为非负数。
一开始我想到的也是01背包，但是这里还有负值，于是我就没有办法了。于是学习到了一个相当于把坐标平移的方法。
因为这里有-1000到0的值，于是我们把它们全都移到右边去，于是变成了非负值0-2000。
解法：
01背包。
但是要注意的是当x>=0时，我们一维形式的01背包是从后往前查找的（今天我才算真正理解为什么需要的是从前往后推，因为我们要保证前面的不会影响后面的。这句话也许有点抽象，但是我们如果从前面往后面更新的话，那么后面dp得到的值就会发生重复叠加的情况，想想二维的形式也许就可以理解，dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]) ，当前位置的dp是由上一行的dp以及加上自己的那种情况而得出的，所以是倒着查找）
当x<0时，这时我们要正着for，因为x<0时，相当于它是在负轴上的，相当于它不取x（x在这里是负值），那么就变成了dp[i-x]+y，就是相当于去后面的数，也就是为了保证后面对前面不造成影响。其实我个人的想法是把它看成与x轴正方向相对称的，这样就是从前往后查询了。
还有对于dp的初始化，这里dp[10000]=0，，因为它相当于是坐标原点，要往两边扩展，所以初始化为0.
#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>#include<vector>using namespace std;#define maxn 200000#define inf 99999999int dp[maxn];int main(){int n;scanf("%d",&n);fill(dp,dp+maxn+1,-inf);dp[100000]=0;for(int i=0;i<n;i++){int x,y;scanf("%d%d",&x,&y);if(x<0&&y<0) continue;if(x>=0){for(int j=maxn;j>=x;j–){dp[j]=max(dp[j],dp[j-x]+y);}}else{for(int j=0;j<=maxn+x;j++){dp[j]=max(dp[j],dp[j-x]+y);}}}int res=-inf;for(int i=100000;i<=maxn;i++){//因为我们要使smart也是非负的，所以要在右半轴上找； if(dp[i]>=0)//dp[i]>=0我们要保证的是fun值也是非负的； res=max(res,dp[i]+i-100000);}if(res<0) printf("0\n");else printf("%d\n",res);}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇poj(1011)——Sticks（经典的dfs+剪枝）下一篇poj(1061)——青蛙的约会（扩展欧几里得算法）
顶0踩0
他们的快乐像贪玩的小孩，游荡到天光却还不肯回来。
