不知为什么，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 ;
}