[TJOI2013]拯救小矮人

题目

首先有一个很假的贪心

我们定义一个人的需求为\(H-h_i-b_i\)，就是这个人需要多少的高度在他下面他才能逃出去

我们趁剩余的高度还够，优先满足需求较高的

显然是错的，可能有一个人身高很高，但是胳膊短，于是需求很大，但是我们满足了这个人就不能提供那么多的高度了

于是我们先按照需求从大到小排个序，之后顺便维护一个\(dp[i][j]\)表示前\(i\)个人里满足了\(j\)个人之后剩下的人生提供的高度最多是多少

对于每个人我们看看他是逃还是不逃就好了

代码

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define re register

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read() {

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

struct P{int h,b,need;}a[2005];

inline int cmp(P A,P B) {return A.need>B.need;}

int dp[2005][2005],beh[2005];

int n,H;

int main() {

	n=read();

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

	H=read();

	for(re int i=1;i<=n;i++) a[i].need=H-a[i].h-a[i].b;

	std::sort(a+1,a+n+1,cmp);

	for(re int i=n;i;i--) beh[i]=beh[i+1]+a[i].h;

	memset(dp,-20,sizeof(dp));dp[0][0]=0;

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

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

			if(dp[i-1][j]+beh[i+1]>=a[i].need) dp[i][j+1]=max(dp[i][j+1],dp[i-1][j]);

			dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i].h);

		}

	}

	for(re int i=n;i>=0;i--)

	if(dp[n][i]>=0) return printf("%d",i),0;

	return 0;

}