首页 > 代码库 > poj 2184 Cow Exhibition (变形的01背包)

poj 2184 Cow Exhibition (变形的01背包)

链接:poj 2184

题意:给定n头牛,每头牛的的智商(si)和幽默感(fi)已知,求在保证智商(S)的和及幽默感(F)的和都为非负的情况下,智商和幽默感(S+T)的最大值

分析:题的本质即从n头牛中选出S>=0&&T>=0时,S+T的最大值

以智商最为容量,幽默感作为价值,因为每头牛只能选一次,就转化01背包了,

dp[i]为智商为i时幽默感的最大值,则状态转移方程为 dp[j]=max(dp[j],dp[j-s[i]]+f[i]);

但是智商总和范围-100000~100000可能为负,而数组下标不能为负,可以将下标整体加100000,存到0~200000中

那么平衡点(即0)变为100000

#include<stdio.h>
#define MIN -999999
int dp[200010];
int main()
{
    int n,i,j,s[105],f[105],max;
    while(scanf("%d",&n)!=EOF){
        for(i=0;i<=200000;i++)
            dp[i]=MIN;
        dp[100000]=0;
        for(i=1;i<=n;i++)
            scanf("%d%d",&s[i],&f[i]);
        for(i=1;i<=n;i++){
            if(s[i]<0&&f[i]<0)        //智商和幽默感都为负,肯定不能被选
                continue;
            if(s[i]>0)             
                for(j=200000;j>=s[i];j--){      //s[i]>0逆序循环
                    if(dp[j-s[i]]+f[i]>dp[j])
                        dp[j]=dp[j-s[i]]+f[i];
                }
            else
                for(j=s[i];j<=200000+s[i];j++)  //s[i]<0顺序循环
                    if(dp[j-s[i]]+f[i]>dp[j])
                        dp[j]=dp[j-s[i]]+f[i];
        }
        max=MIN;
        for(i=100000;i<=200000;i++)      //求幽默感和智商都为正的总和最大值
            if(dp[i]>=0&&dp[i]+i-100000>max)     
                max=dp[i]+i-100000;      //因为下标都加了100000,所有要减
        if(max==MIN)
            max=0;
        printf("%d\n",max);
    }
    return 0;
}