bzoj3174【TJOI2013】拯救小矮人

description

一群小矮人掉进了一个很深的陷阱里，由于太矮爬不上来，于是他们决定搭一个人梯。即：一个小矮人站在另一小矮人的 肩膀上，知道最顶端的小矮人伸直胳膊可以碰到陷阱口。对于每一个小矮人，我们知道他从脚到肩膀的高度ai，并且他的胳膊长度为bi。陷阱深度为h。如果我 们利用矮人1，矮人2，矮人3,。。。矮人k搭一个*，满足a1+a2+a3+....+ak+bk>=h,那么矮人k就可以离开陷阱逃跑了，一 旦一个矮人逃跑了，他就不能再搭人梯了。
我们希望尽可能多的小矮人逃跑， 问最多可以使多少个小矮人逃跑。

input

第一行一个整数n， 表示矮人的个数，接下来n行每一行两个整数ai和bi，最后一行是h。（ai，bi，h<=10^5）

output

一个整数表示对多可以逃跑多少小矮人

sample input

样例1

2
20 10
5 5
30

样例2
2
20 10
5 5
35

sample output

样例1
2

样例2
1

hint

数据范围

30%的数据 n<=200

100%的数据 n<=2000

贪心+dp

感性地理解一下，a[i]+b[i]较大的小矮人逃跑的能力更强，所以我们要先让a[i]+b[i]小的人尽可能先逃跑。于是可以想到按a[i]+b[i]从小到大排序，然后贪心计算。但这个贪心显然是有问题的，所以我们考虑用dp解决贪心的不足。

贪心的不足之处在于当前的小矮人的a[i]还会对后面的小矮人产生影响，所以我们可以令f[i]表示逃跑了i个小矮人剩余a[i]和的最大值。在更新f数组的同时也就计算出了答案。

注意：f数组要逆向更新。

#include
#include
#include
#include
#include
#include
#define f(i,j,n) for(int i=j;i<=n;i++)
#define d(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 2005
using namespace std;
int n,h,ans,f[maxn];
struct data{int x,y;}a[maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline bool cmp(data a,data b)
{
	return a.x+a.y=h) f[j+1]=max(f[j+1],f[j]-a[i].x);
		if (f[ans+1]>=0) ans++;
	}
	printf("%d\n",ans);
	return 0;
}