Description
一群小矮人掉进了一个很深的陷阱里，由于太矮爬不上来，于是他们决定搭一个人梯。即：一个小矮人站在另一小矮人的 肩膀上，知道最顶端的小矮人伸直胳膊可以碰到陷阱口。对于每一个小矮人，我们知道他从脚到肩膀的高度Ai，并且他的胳膊长度为Bi。陷阱深度为H。如果我 们利用矮人1，矮人2，矮人3,。。。矮人k搭一个梯子，满足A1+A2+A3+….+Ak+Bk>=H,那么矮人k就可以离开陷阱逃跑了，一 旦一个矮人逃跑了，他就不能再搭人梯了。
我们希望尽可能多的小矮人逃跑， 问最多可以使多少个小矮人逃跑。
Input
第一行一个整数N， 表示矮人的个数，接下来N行每一行两个整数Ai和Bi，最后一行是H。（Ai，Bi，H<=10^5）
Output
一个整数表示对多可以逃跑多少小矮人
Sample Input
样例1
2
20 10
5 5
30
样例2
2
20 10
5 5
35
Sample Output
样例1
2
样例2
1
HINT
数据范围
30%的数据 N<=200
100%的数据 N<=2000
拿到这道题我就想起了国王游戏和POJ 的Cow Acrobats
然后就想了想加起来贪心对不对，发现是对的
如果觉得这道题的贪心思路有点Confusing，可以看下我的naive的证明：
设i,j是最上面的两个小矮人，且i是最上面的那么若i.a+i.b<j.a+j.b，则j放在i的上面明显可以够到更高的地方所以i应该在j的上面当且仅当i.a+i.b>=j.a+j.b证毕！
相信你们想想就没问题了。
下面是代码：
/**************************************************************
Problem: 3174
User: geng4512
Language: C++
Result: Accepted
Time:28 ms
Memory:1296 kb
****************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define MAXN 2005
using namespace std;
struct Node {
int a, b;
inline bool operator < (const Node &r) const { return a + b < r.a + r.b; }
} h[MAXN];
int n,H,sum,f[MAXN];
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++ i)
scanf("%d%d", &h[i].a, &h[i].b);
sort(h+1,h+n+1);
memset(f,-1,sizeof f);
f[0]=0;
for(int i = 1; i <= n; ++ i) f[0]+=h[i].a;
scanf("%d",&H);
int sum=0;
for(int i = 1; i <= n; ++ i)
for(int j = sum; j >= 0; -- j) {
if(f[j]+h[i].b>=H)
f[j+1] = max(f[j+1], f[j]-h[i].a);
if(f[sum+1] >= 0) sum ++;
}
printf("%d", sum);
return 0;
}