bzoj3174【TJOI2013】拯救小矮人

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;
}