【BZOJ3174】[TJOI2013]拯救小矮人（贪心，动态规划）

题面

BZOJ

洛谷

题解

我们定义一个小矮人的\(A_i+B_i\)为它的逃跑能力。

我们发现，如果有两个小矮人\(x,y\)，逃跑能力\(x<y\)，并且在当前方案中最终\(x\)和\(y\)都跑出去了，那么显然让\(x\)先跑出去不会更差。

那么把所有人按照逃跑能力排序，这样子我们只需要从前往后选择若干人让他们顺次逃跑就好了。

设\(f[i][j]\)表示当前考虑到了前\(i\)个人，一共跑出去了\(j\)个人之后剩下的人梯的最大高度，转移的时候枚举一下每个人是否跑出去就好了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAX 2020

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,H;

struct Node{int a,b;}p[MAX];

bool operator<(Node a,Node b){return a.a+a.b<b.a+b.b;}

int f[MAX][MAX],s[MAX];

int main()

{

	n=read();for(int i=1;i<=n;++i)p[i].a=read(),p[i].b=read();

	H=read();sort(&p[1],&p[n+1]);

	for(int i=n;i;--i)s[i]=s[i+1]+p[i].a;

	memset(f,-63,sizeof(f));f[0][0]=0;

	for(int i=1;i<=n;++i)

		for(int j=0;j<i;++j)

		{

			f[i][j]=max(f[i][j],f[i-1][j]+p[i].a);

			if(f[i-1][j]+s[i+1]+p[i].a+p[i].b>=H)f[i][j+1]=max(f[i][j+1],f[i-1][j]);

		}

	for(int i=n;~i;--i)if(f[n][i]>=0){printf("%d\n",i);break;}

	return 0;

}