2075 yh女朋友的危机、2544 拯救小矮人

Codevs2075和2544是一道题，直接A过。

2075 yh女朋友的危机

 

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 钻石 Diamond

题解

 查看运行结果

 

 

题目描述 Description

不知为什么，yh的女朋友们都掉入了一个深度为h的天坑。由于天坑太深，yh的女朋友们无法爬出去，于是她们决定用搭人梯的方式脱困。我们知道yh的每位女朋友从脚到肩膀的高度ai，以及肩膀到伸直手臂的距离bi。由k个人搭成的人梯的高度为a1+a2+…+ak+bk;当人梯高度大于等于h时，第k个人就可以爬出天坑，并再也不进来。你能帮助他的女朋友们安排一个方案，使得最多的女朋友能爬出天坑吗？

输入描述 Input Description

第一行一个整数n，表示有n个女朋友掉进坑里

第2行到第n+1行，每行两个整数，表示女朋友从脚到肩膀的距离ai和从肩膀到伸直手臂的距离bi。

第n+2行为一个整数h，表示天坑深度为h。

输出描述 Output Description

输出一行，一个整数，表示最多能爬出天坑的女朋友的数量

样例输入 Sample Input

2

20 10

5 5

35

样例输出 Sample Output

1

数据范围及提示 Data Size & Hint

对于40%数据，n≤100

对于100%数据，n≤2000，ai，bi，h≤100000

分类标签 Tags 点此展开 

 

动态规划 贪心

 

吐槽：管理员贴的什么标签啊

ps:本人实测，贪心貌似过不了（也可能是个人技术问题）。

dp AC代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100100
struct node{
    int a,b;
    node(int a=0,int b=0):a(a),b(b){}
}p[N];
int n,h,f[N<<1],ans;
inline int cmp(const node &x,const node &y){
    return x.a+x.b<y.a+y.b;
}
int main(){
    memset(f,-1,sizeof f);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&p[i].a,&p[i].b);
    scanf("%d",&h);
    f[0]=0;
    for(int i=1;i<=n;i++) f[0]+=p[i].a;
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++){
        for(int j=ans;j>=0;j--){
            if(f[j]+p[i].b>=h)
                f[j+1]=max(f[j+1],f[j]-p[i].a);
            if(f[ans+1]>=0) ans++;
        }
    }
    printf("%d
",ans);
    return 0;
}

2544 拯救小矮人

 

2013年省队选拔赛天津市队选拔赛（也就是dp难想点）

 时间限制: 1 s

 空间限制: 256000 KB

 题目等级 : 大师 Master

题解

 查看运行结果

 

 

题目描述 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

2

样例1

1

数据范围及提示 Data Size & Hint

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

分类标签 Tags 点此展开 

 

天津 省队选拔赛 市队选拔赛 2013年

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100100
struct node{
    int a,b;
    node(int a=0,int b=0):a(a),b(b){}
}p[N];
int n,h,f[N<<1],ans;
inline int cmp(const node &x,const node &y){
    return x.a+x.b<y.a+y.b;
}
int main(){
    memset(f,-1,sizeof f);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&p[i].a,&p[i].b);
    scanf("%d",&h);
    f[0]=0;
    for(int i=1;i<=n;i++) f[0]+=p[i].a;
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++){
        for(int j=ans;j>=0;j--){
            if(f[j]+p[i].b>=h)
                f[j+1]=max(f[j+1],f[j]-p[i].a);
            if(f[ans+1]>=0) ans++;
        }
    }
    printf("%d
",ans);
    return 0;
}