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、这题是怎么被评到绿题去的？？我怎么做着和黑题一样