首先我们按照逃跑能力($a+b$)排序，然后把逃跑能力强的放后面
然后dp,设$f[i]$表示在$i$个人逃跑后剩下的人梯最高高度
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2005;
int n,h,f[N],ans=0;
struct Data{
int a,b;
friend bool operator<(Data A,Data B){return A.a+A.b<B.a+B.b;}
}man[N];
int main(){
freopen("3174.in","r",stdin);
freopen("3174.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d %d",&man[i].a,&man[i].b);
scanf("%d",&h);
sort(man+1,man+n+1);
memset(f,-1,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++)f[0]+=man[i].a;
for(int i=1;i<=n;i++){
for(int j=ans;j>=0;j--){
if(f[j]+man[i].b>=h)f[j+1]=max(f[j+1],f[j]-man[i].a);
if(f[ans+1]>=0)ans++;
}
}
printf("%d\n",ans);
return 0;
}
评论 (0)
