poj 2484 Cow Exhibition 【变形0-1背包】-蒲公英云

poj 2484 Cow Exhibition 【变形0-1背包】

题目：poj 2484 Cow Exhibition

题意：给出n头牛，每头牛有一个幸运值 si 和聪明值 ti ，现在要选出一些牛，让两个值的和最大，前提是sum（si）和sum（ti）都是非负值。

分析：此题数据量不大，可以暴搜+剪枝水过。

这里要说的是0-1背包的思想，这个题目明显的变形就是物品有两个属性值，而且都要选最大的。

那么我们可不可以把一个值固定下来来求另一个值的最大值，根据0-1背包的思想，定义状态：dp【i】表示装入一些物品使得sum（si）的时候最大的sum（ti）的值。

那么状态转移方程为dp【i+si】 = max（dp【i+si】，dp【i】+ti），正好表示一个物品的两种选择。

ac代码：

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 210000;
const int pos = 100000;
int dp[N];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(dp,-0x3f3f3f3f,sizeof(dp));
        dp[pos] = 0;
        int ma = pos,mi = pos;
        for(int i=0;i<n;i++)
        {
            int s,t;
            scanf("%d%d",&s,&t);
            if(s>0){
                for(int f=ma ;f>=mi;f--)
                    dp[f+s] = max(dp[f+s],dp[f]+t);
                ma+=s;
            }
            else{
                for(int f = mi;f<=ma;f++)
                    dp[f+s] = max(dp[f+s],dp[f]+t);
                mi+=s;
            }
        }
        int ans = 0;
        for(int i=pos;i<=ma;i++)
            if(dp[i]>=0)
                ans = max(ans,i-pos+dp[i]);
        printf("%d\n",ans);
    }
    return 0;
}

搜索超时代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 210000;
const int pos = 100000;
struct Node
{
    int s,t;
};
vector<Node> v;
int cmp(Node a,Node b)
{
    if(a.s!=b.s)
        return a.s>b.s;
    if(a.t!=b.t)
        return a.t>b.t;
}
int ans;
void dfs(int i,int sums,int sumt)
{
    if(i==v.size())
        return ;
    if(sums>=0 && sumt>=0)
        ans = max(ans,sums+sumt);
    if(sums<0 && v[i].s<=0)
        return ;
    dfs(i+1,sums,sumt);
    dfs(i+1,sums+v[i+1].s,sumt+v[i+1].t);
}
int main()
{
    int n;
    int sums = 0,sumt = 0;
    while(~scanf("%d",&n))
    {
        for(int i=0;i<n;i++)
        {
            int s,t;
            scanf("%d%d",&s,&t);
            if(s>=0 && t>=0)
            {
                sums+=s,sumt+=t;
            }
            else if(s<=0 && t<=0)
                continue;
            else
                v.push_back((Node){s,t});
        }
        sort(v.begin(),v.end(),cmp);
        ans = 0;
        dfs(0,0,0);
        dfs(0,v[0].s,v[0].t);
        printf("%d\n",ans+sums+sumt);
    }
    return 0;
}