5
17
2016
0

[BZOJ3174] [Tjoi2013]拯救小矮人

首先我们按照逃跑能力($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;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 432

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com