拯救小矮人(codevs 2544)

题目描述 Description

一群小矮人掉进了一个很深的陷阱里，由于太矮爬不上来，于是他们决定搭一个人梯。即：一个小矮人站在另一小矮人的肩膀上，知道最顶端的小矮人伸直胳膊可以碰到陷阱口。对于每一个小矮人，我们知道他从脚到肩膀的高度Ai，并且他的胳膊长度为Bi。陷阱深度为H。如果我们利用矮人1，矮人2，矮人3,。。。矮人k搭一个梯子，满足A1+A2+A3+....+Ak+Bk>=H,那么矮人k就可以离开陷阱逃跑了，一旦一个矮人逃跑了，他就不能再搭人梯了。

我们希望尽可能多的小矮人逃跑，问最多可以使多少个小矮人逃跑。

输入描述 Input Description

第一行一个整数N，表示矮人的个数，接下来N行每一行两个整数Ai和Bi，最后一行是H。（Ai，Bi，H<=10^5）

输出描述 Output Description

一个整数表示对多可以逃跑多少小矮人

样例输入 Sample Input

样例1

2
20 10
5 5
30

样例2
2
20 10
5 5
35

样例输出 Sample Output

样例1

数据范围及提示 Data Size & Hint

数据范围
30%的数据 N<=200
100%的数据 N<=2000

/*
  由题意可以知道，e[i].a+e[i].b大的跑出来的能力强，所以我们让e[i].a+e[i].b小的
  优先跑出来，但这样的结果一定不是最优，所以要用DP来进行加强；f[i]表示已经出来i个人的时候最大的身高和，f[0]=Σe[i].a。 
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define M 2010
using namespace std;
int n,m,f[M];
struct node
{
    int x,y;
};node e[M];
int cmp(const node&a,const node&b)
{
    return (a.x+a.y)<(b.x+b.y);
}
int main()
{
    memset(f,-1,sizeof(f));
    f[0]=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
      scanf("%d%d",&e[i].x,&e[i].y),
      f[0]+=e[i].x;
    scanf("%d",&m);
    sort(e+1,e+n+1,cmp);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=ans;j>=0;j--)
          if(f[j]+e[i].y>=m)
            f[j+1]=max(f[j+1],f[j]-e[i].x);
        if(f[ans+1]>=0)ans++;
    }
    printf("%d",ans);
    return 0;
}

View Code