[BZOJ3174] [Tjoi2013]拯救小矮人

题目描述

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

题目分析

神思路 贪心+DP
我们先按它的身高+手长值递增排序,尽量让出不去的人先出去
然后就可以DP
设f[i]表示成功出去i个小矮人后,剩下的人塔的最大高度.

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
struct your
{
    int a,b;
}a[100010];
bool cmp(your j,your k)
{
    return j.a+j.b<k.a+k.b;
}
int ans;
int f[100010];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].a,&a[i].b);
    scanf("%d",&m);
    sort(a+1,a+n+1,cmp);
    f[0]=0;
    for(int i=1;i<=n;i++) f[0]+=a[i].a; 
    for(int i=1;i<=n;i++)
        for(int j=ans;j>=0;j--)
            if(f[j]+a[i].b>=m)
            {
                ans=max(ans,j+1);
                f[j+1]=max(f[j+1],f[j]-a[i].a);
            }
    printf("%d",ans);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注