6
5
2014
4

3174: [Tjoi2013]拯救小矮人

首先是题目:

3174: [Tjoi2013]拯救小矮人

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 275  Solved: 128
[Submit][Status]

Description

 

Input

 

Output

 

Sample Input

 

Sample Output

 

HINT

好了不逗比了……

bzoj上没有题面……

求大神补上……

拯救小矮人
• 输入输出文件:dwarf.in/dwarf.out
• 源文件名:dwarf.cpp/dwarf.c/dwarf.pas
• 时间限制:1s
一群小矮人掉进了一个很深的陷阱里。由于太矮爬不上来,于是他们决
定搭一个人梯。即:一个矮人站在另一个矮人的肩膀上,直到最顶端的矮人
伸直胳膊可以碰到陷阱口。对于每一个矮人,我们知道他从脚到肩膀的高度
为Ai,并且他的胳膊长度为Bi。陷阱深度为H。如果我们利用矮人1,矮人2,
矮人3...矮人k搭一个梯子,满足A1 + A2 + A3 + ... + Ak + Bk ≥ H,那么矮
人k就可以离开陷阱逃跑了。一旦一个矮人逃跑,他就不能再搭人梯了。
我们希望尽可能多的矮人能够离开陷阱。请你帮助小矮人计算最多可以逃
跑多少个小矮人。
输入
第一行一个整数N,表示矮人的个数。接下来N行每一行两个整数Ai和Bi。
最后一行是H。(Ai,Bi,H ≤ 10^5)
输出
一个整数,表示最多可以逃跑多少个小矮人。
样例输入1
2
20 10
5 5
30
样例输出1
2
样例输入2
2
20 10
5 5
35
样例输出2
1
数据范围
30%的数据,N ≤ 200
100%的数据,N ≤ 2000
从pdf上复制过来的……
格式无视掉……
dp……
f[i]表示逃跑i个人后剩下的人梯最高的高度……
设当前为第x人
if (f[i]+Bx>=H)//第x人可以逃跑
f[i+1]=max(f[i+1],f[i]-Ax);//答案更新

但是显然需要先根据贪心思想进行排序……

根据Ai+Bi从小到大排序……

不要问我为什么……

自己yy……

假设陷阱高度为50,有3个人,

A1=20,B1=20;

A2=40,B2=9;

A3=1,B3=50;

显然应该先让第一个人跑掉,然后是第二个人,然后第三个人

让Ai+Bi小的先跑掉……

Ai+Bi越大,底下垫的人需要的高度就越小,可以先让更多的人跑……

代码:

/**************************************************************
    Problem: 3174
    User: sxczf
    Language: C++
    Result: Accepted
    Time:16 ms
    Memory:828 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <set>
using namespace std;
inline int maxx(const int &a,const int &b){if (a>b)return a;return b;}
inline int minn(const int &a,const int &b){if (a<b)return a;return b;}
int b,c,d,e,f[2005],g,h,i,j,k,l,m,n;
struct czf{int a,b;}a[2005];
inline bool cmp(czf a,czf b){return a.a+a.b<b.a+b.b;}
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d%d",&a[i].a,&a[i].b);
    sort(a+1,a+1+n,cmp);
    scanf("%d",&m);
    for(i=1;i<=n;i++)f[0]+=a[i].a;
    for(i=1;i<=n;i++)f[i]=-1;
    h=0;
    for(i=1;i<=n;i++){
        for(j=h;j>=0;j--)
        if (f[j]+a[i].b>=m){
            if (f[j]-a[i].a>f[j+1])
            f[j+1]=f[j]-a[i].a;
        }
        if (f[h+1]>=0)h++;
    }
    printf("%d",h);
    return 0;
}

 

Category: BZOJ | Tags: | Read Count: 1125
Avatar_small
sxczf 说:
2014年6月12日 11:17

@悄然离去: 跪烂qiaoranpenxiang神犇!!!!!

sxczf 说:
2014年6月12日 17:32

@悄然离去: qiaoranpenxiang真是太神了!!!!!!


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com