題目大意：
有100頭牛，每頭牛有Fi, Si兩個(gè)值。Fi, Si 范圍是-1000~1000
選出一些牛，確保這些牛的 Sum{Fi} + Sum{Si} 最大
同時(shí) Sum{Fi}，Sum{Si} 都不能為負(fù)
思路：
一開始看到范圍那么大，首先就否決背包了！想了一個(gè)不大靈光的解法，結(jié)果wa啦。。
后來(lái)看了Discuss。發(fā)現(xiàn)都是用背包過(guò)的，是最簡(jiǎn)單的一維背包！居然還有人是搜索過(guò)的！
但是，如果數(shù)據(jù)bt點(diǎn)的話，背包是不可能過(guò)的！但是USACO的題目感覺數(shù)據(jù)都弱一點(diǎn)，哈哈！
代碼爛，63ms
#include <stdio.h>
struct 
{
int val, used;
} _slot[100024*2], *slot = &_slot[100024];
int up, down;
int main()
{
int n, s, f, i;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &n);
up = down = 0;
while (n--) {
scanf("%d%d", &s, &f);
if (s < 0 && f < 0)
continue;
if (s < 0) {
for (i = down; i <= up; i++) {
if (!slot[i].used)
continue;
if (!slot[i + s].used || f + slot[i].val > slot[i + s].val) {
slot[i + s].used = 1;
slot[i + s].val = f + slot[i].val;
}
}
down += s;
} else {
for (i = up; i >= down; i--) {
if (!slot[i].used)
continue;
if (!slot[i + s].used || f + slot[i].val > slot[i + s].val) {
slot[i + s].used = 1;
slot[i + s].val = f + slot[i].val;
}
}
up += s;
}
if (!slot[s].used || slot[s].val < f) {
slot[s].used = 1;
slot[s].val = f;
}
}
s = 0;
for (i = 0; i <= up; i++) {
if (slot[i].used && slot[i].val >= 0 && slot[i].val + i > s)
s = slot[i].val + i;
}
printf("%d\n", s);
return 0;
}