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

妖狐艹你老母 2022-08-13 13:50 17阅读 0赞

题目：[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;
    }

[poj 2484 Cow Exhibition]: http://poj.org/problem?id=2184