bzoj 3174: [Tjoi2013]拯救小矮人

Description

一群小矮人掉进了一个很深的陷阱里，由于太矮爬不上来，于是他们决定搭一个人梯。即：一个小矮人站在另一小矮人的 肩膀上，知道最顶端的小矮人伸直胳膊可以碰到陷阱口。对于每一个小矮人，我们知道他从脚到肩膀的高度Ai，并且他的胳膊长度为Bi。陷阱深度为H。如果我 们利用矮人1，矮人2，矮人3,。。。矮人k搭一个梯子，满足A1+A2+A3+....+Ak+Bk>=H,那么矮人k就可以离开陷阱逃跑了，一 旦一个矮人逃跑了，他就不能再搭人梯了。

我们希望尽可能多的小矮人逃跑， 问最多可以使多少个小矮人逃跑。

解题报告:

用时:1h20min,3WA

这题一开始写了个错的，首先显然是可以按\(ai+bi\)排序，因为能力强的要放在最后逃跑，然后简单的认为:能出去的就出去，不能出去的先丢入堆中，如果当前的矮人逃不出去，那么就用堆中的元素帮他出去，但是显然是错的....然后发现这个东西需要决策.然后想到DP，天真以为\(f[i]=f[j]+1\),如果\(j-i\)中的矮人堆起来可以帮\(i\)逃出去,然而还是不对，参考题解的状态.\(f[i]\)为逃出\(i\)人，剩下的人\(ai\)和的最大值.然后想到背包，\(f[j+1]=f[j]-a[i]\)，最后找到合法的最大\(j\)即可

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <queue>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

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

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

using namespace std;

const int N=2005;

struct node{

	int x,y;

	bool operator <(const node &pr)const{

		return x+y>pr.x+pr.y;

	}

}a[N];

int f[N];

void work()

{

	int n,H;

	scanf("%d",&n);

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

		scanf("%d%d",&a[i].x,&a[i].y);

	sort(a+1,a+n+1);scanf("%d",&H);

	int ans=0;

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

	for(int i=1;i<=n;i++)f[0]+=a[i].x;

	for(int i=n;i>=1;i--){

		for(int j=ans;j>=0;j--)

			if(f[j]+a[i].y>=H)

			f[j+1]=Max(f[j+1],f[j]-a[i].x);

		if(f[ans+1]>=0)ans++;

	}

	printf("%d\n",ans);

}

int main()

{

	work();

	return 0;

}