传送门

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;

}