不知为什么,yh的女朋友们都掉入了一个深度为h的天坑。由于天坑太深,yh的女朋友们无法爬出去,于是她们决定用搭人梯的方式脱困。我们知道yh的每位女朋友从脚到肩膀的高度ai,以及肩膀到伸直手臂的距离bi。由k个人搭成的人梯的高度为a1+a2+…+ak+bk;当人梯高度大于等于h时,第k个人就可以爬出天坑,并再也不进来。你能帮助他的女朋友们安排一个方案,使得最多的女朋友能爬出天坑吗?
第一行一个整数n,表示有n个女朋友掉进坑里
第2行到第n+1行,每行两个整数,表示女朋友从脚到肩膀的距离ai和从肩膀到伸直手臂的距离bi。
第n+2行为一个整数h,表示天坑深度为h。
输出一行,一个整数,表示最多能爬出天坑的女朋友的数量
2
20 10
5 5
35
1
对于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=,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 ;
}
一群小矮人掉进了一个很深的陷阱里,由于太矮爬不上来,于是他们决定搭一个人梯。即:一个小矮人站在另一小矮人的肩膀上,知道最顶端的小矮人伸直胳膊可以碰到陷阱口。对于每一个小矮人,我们知道他从脚到肩膀的高度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
样例2
2
20 10
5 5
35
样例1
2
样例1
1
数据范围
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 ;
}