【DP】【P2340】奶牛会展

传送门

Description

奶牛想证明它们是聪明而风趣的。为此，贝西筹备了一个奶牛博览会，她已经对N 头奶牛进行了面试，确定了每头奶牛的智商和情商。

贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果，所以贝西不希望出展奶牛的智商之和小于零，或情商之和小于零。

满足这两个条件下，她希望出展奶牛的智商与情商之和越大越好，请帮助贝西求出这个最大值。

Input

第一行：单个整数N，
第二行到第N + 1 行：第i + 1 行有两个整数：Si 和Fi，表示第i 头奶牛的智商和情商。

Output

　　单个整数：表示情商与智商和的最大值。贝西可以不让任何奶牛参加展览，如果这样做是最好的，输出0

Sample Input

-

 -

 -

- -

Sample Output

Hint

选择第一头，第三头，第四头奶牛，智商和为−5+6+2 = 3，情商和为7−3+1 = 5。再加

入第二号奶牛可使总和提升到10，不过由于情商和变成负的了，所以是不允许的

1 ≤ N ≤ 400；−1000 ≤ Si; Fi ≤ 1000

Solution

　　一眼看出这是个背包，然后…………然后呢？？？

　　最初想法是些bool型背包，发现爆空间（8000000*8000000）直接GG，于是放弃，想到之前的栈做法写了一个栈，使用map判重，详见代码一。然后发现map的复杂度过高，并且占据的空间依然很大，于是GG。

　　考虑状态压缩。

　　由于数组的下标可以存储一定的信息，我们使用f[i]的值存储s=i时最大的f值，由于要求结果最大，s一定时f显然越大越好。于是满足无后效性。注意要对下标进行平移，使用maxup和maxdown记录当前更新的上限和下限，每次进行转移。

　　剪枝：如果s和f都小于零，那么你们今日知罪又有何用？显然他们对答案不会有任何好的贡献，直接continue即可。

Code

#include<map>

#include<cstdio>

#include<algorithm>

#define maxn 10010

#define maxm 4000010

inline void qr(int &x) {

    char ch=getchar();int f=;

    while(ch>''||ch<'')    {

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')    x=(x<<)+(x<<)+(ch^),ch=getchar();

    x*=f;

    return;

}

inline int max(const int &a,const int &b) {if(a>b) return a;else return b;}

inline int min(const int &a,const int &b) {if(a<b) return a;else return b;}

inline int abs(const int &x) {if(x>) return x;else return -x;}

inline void swap(int &a,int &b) {

    int c=a;a=b;b=c;return;

}

struct Frog {

    int s,f;

    Frog() {s=f=;}

    Frog(int x,int y) {s=x;f=y;}

};

Frog frog[maxm];

int top=;

inline bool operator <(const Frog &a,const Frog &b) {

    if(a.s^b.s)    return a.s<b.s;

    return a.f<b.f;

}

bool ins[maxn][maxn];

Frog temp;

int n,a,b;

inline bool cmp(const Frog &a,const Frog &b) {

    int sa=a.s+a.f,sb=b.s+b.f;

    return sa<sb;

}

int main() {

    qr(n);

    for(int i=;i<=n;++i) {

        a=b=;qr(a);qr(b);

        if(a<=&&b<=)    continue;

        int t=top;

        for(int j=;j<=t;++j) {

            int da=frog[j].s+a,db=frog[j].f+b;

            temp=Frog(da,db);

            if(ins[da+][db+])    continue;

            ins[da+][db+]=true;

            frog[++top]=temp;

        }

    }

    std::sort(frog+,frog++top,cmp);

    for(int i=top;i;--i) {

        if(frog[i].s>=&&frog[i].f>=) {

            printf("%d\n",frog[i].s+frog[i].f);return ;

        }

    }

    putchar('');putchar('\n');

    return ;

}

代码1 map 45分

#include<cstdio>

#include<cstring>

#define maxn 800005

inline void qr(int &x) {

    char ch=getchar();int f=;

    while(ch>''||ch<'')    {

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')    x=(x<<)+(x<<)+(ch^),ch=getchar();

    x*=f;

    return;

}

inline int max(const int &a,const int &b) {if(a>b) return a;else return b;}

inline int min(const int &a,const int &b) {if(a<b) return a;else return b;}

inline int abs(const int &x) {if(x>) return x;else return -x;}

inline void swap(int &a,int &b) {

    int c=a;a=b;b=c;return;

}

int n,frog[maxn],a,b,ans,maxup=,maxdown=;

const int away=;

int main() {

    qr(n);

    std::memset(frog,-0x3f,sizeof frog);frog[away]=;

    for(int i=;i<=n;++i) {

        a=b=;qr(a);qr(b);

        if(a<=&&b<=)    continue;

        int dd=maxdown+a;

        if(a>) {

            for(int j=maxup+a;j>=dd;--j)

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

            maxup+=a;

        }

        else {

            for(int j=dd;j<=maxup;++j)

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

            maxdown+=a;

        }

    }

    for(int i=away;i<=maxup;++i)

    {

        if(frog[i]>=)    ans=max(frog[i]+i-away,ans);

    }

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

    return ;

}

Summary

　　1、使用map且结构体为第一关键字时，需要重载合法的小于号供map使用，如果需要规则不同的sort，需要手写比较函数，不能重载运算符。

　　　2、二维dp且空间较大的时候可以考虑状压，把其中一维作为下标处理。

　　　3、这题是怎么被评到绿题去的？？我怎么做着和黑题一样

巴特西