【BZOJ-3174】拯救小矮人 贪心 + DP

时间：2023-03-08 16:25:04

3174: [Tjoi2013]拯救小矮人

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 686  Solved: 357
[Submit][Status][Discuss]

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

Source

Solution

一年前做的一道题...贪心+DP...当时不会证，现在会证了。

首先贪心的按a[i].h+a[i].l<a[j].h+a[j].l排序，然后按此顺序DP

至于证明，很直观的理解就是： 如果xy和yx都可以出去一个，那么留下一个h+l较大的那个显然更有可能在之后出去。

那么我们分两种情况讨论一下就可以。 稍微想一下就能想到。

设f[i]表示能逃出的人中，第i个人逃走后剩下的高度h

然后按照那个顺序枚举当前第i个人即可，当前第i个人可以更新f[j]+a[i].l>=H的人。

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

inline int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define MAXN 2010

struct Node{int h,l;}a[MAXN];

bool cmp(Node A,Node B) {return A.h+A.l<B.h+B.l;}

int f[MAXN],N,H,ans;

int main()

{

    N=read();

    for (int i=; i<=N; i++) a[i].h=read(),a[i].l=read();

    H=read();

    sort(a+,a+N+,cmp);

    memset(f,-,sizeof(f)); f[]=;

    for (int i=; i<=N; i++) f[]+=a[i].h;

    for (int i=; i<=N; i++)

        for (int j=ans; j>=; j--)

            {

                if (f[j]+a[i].l>=H) f[j+]=max(f[j+],f[j]-a[i].h);

                if (f[ans+]>=) ans++;

            }

    printf("%d\n",ans);

    return ;

}

我就想用用奇淫技巧卡卡时....然后竟然WA了半天....

相关文章