传送门

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;
}

05-11 13:05