poj2184 01背包变形，价值为可为负数

题目链接：http://poj.org/problem?id=2184

题意：每行给出si和fi，代表牛的两个属性，然后要求选出几头牛，满足S与F都不能为负数的条件下，使S与F的和最大。

tips：动态规划中状态维和值是可以相互转化的。状态维过多，效率低的时候，可以把将其转化为数组值；同理，数组值不唯一无法规划时，可以增加状态维使状态更详细。

这道题有两个值，把其中一个值转换为状态维。注意价值和体积都可以为负数的时候是怎么求。

代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define ll long long

const int INF=0x3f3f3f3f;

const int maxn=2e5+;

const int x=1e5;

const int y=2e5;

int dp[maxn];

int a[],b[];

int main()

{

    int N;

    while(scanf("%d",&N)==)

    {

        for(int i=; i<=N; i++)

            scanf("%d%d",&a[i],&b[i]);

        for(int i=; i<maxn; i++) ///因为是用数组的维数代表价值，所以要求必须装满

            dp[i]=-INF;        ///这里不可以用-1来标记，因为价值可能是负的

        dp[x]=;             ///刚好什么都没装的状态

        for(int i=; i<=N; i++)

        {

            if(a[i]>){

                for(int j=y; j>=a[i]; j--)

                if(dp[j-a[i]]>-INF)

                dp[j]=max(dp[j],dp[j-a[i]]+b[i]);

            }

            else{

                for(int j=; j<=y+a[i]; j++)

                if(dp[j-a[i]]>-INF)

                dp[j]=max(dp[j],dp[j-a[i]]+b[i]);

            }

        }

        int ans=-INF;

        for(int i=x; i<=y; i++)

        if(dp[i]>=) ans=max(ans,i-x+dp[i]);

        printf("%d\n",ans);

    }

    return ;

}