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 点此展开

 
 
吐槽:管理员贴的什么标签啊
2075 yh女朋友的危机、2544 拯救小矮人-LMLPHP

ps:本人实测,贪心貌似过不了(也可能是个人技术问题)。

dp AC代码:

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

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

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