记录编号	18433	评测结果	AAAAAAAAAA
题目名称	越狱	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	2.665 s
提交时间	2010-09-14 20:07:07	内存使用	0.60 MiB

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>

using namespace std;
struct station
{
	int d,w;
}P[20001];

int cmp(const void *a,const void *b)
{
	station *aa=(station *)a;
	station *bb=(station *)b;
	return bb->d - aa->d;
}

int n;
int f[2][20001];
bool y[2][20001];
int main()
{
	freopen("prisonbreak.in","r",stdin);
	freopen("prisonbreak.out","w",stdout);
	scanf("%d",&n);n++;
	for (int i=n-1;i>=0;i--) scanf("%d%d",&P[i].d,&P[i].w);
	qsort(P,n+1,sizeof(P[0]),cmp);
	f[0][0]=P[0].w;y[0][0]=true;
	for (int i=1;i<=n;i++)
	{
		int t=i & 1;
		memset(f[t],0,sizeof(f[t]));
		memset(y[t],0,sizeof(y[t]));
		for (int j=i-1;j>=0 && y[1-t][j] && f[1-t][j]-(P[i-1].d-P[i].d)>=0;j--)
		{
			if (f[t][j]<f[1-t][j]-(P[i-1].d-P[i].d))
			f[t][j]=f[1-t][j]-(P[i-1].d-P[i].d);
			y[t][j]=y[t][j+1]=true;
			if (f[t][j+1]<f[t][j]+P[i].w)
			f[t][j+1]=f[t][j]+P[i].w;
		}
	}
	int i;
	for (i=0;i<=n;i++)
	{
		if (y[n & 1][i]) {printf("%d\n",i);break;}
	}
	if (i>n) printf("-1\n");
}