比赛 NOIP2008集训模拟5 评测结果 AWTTTTTTTA
题目名称 越狱 最终得分 20
用户昵称 BYVoid 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2008-11-14 09:22:43
显示代码纯文本
#include <iostream>

using namespace std;

const int MAXN=10001;
const int MAXM=3001;
const int INF=0x7FFFFFFF;

struct Station
{
	int d,o;
};

int N,L,P,Ans=INF;
Station S[MAXN];
int F[MAXN][MAXM];
int Max[MAXN],Min[MAXN];

inline int cmp(const void *a,const void *b)
{
	return ((Station * )a)->d - ((Station * )b)->d;
}

void init()
{
	int i;
	freopen("prisonbreak.in","r",stdin);
	freopen("prisonbreak.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d%d",&S[i].d,&S[i].o);
	}
	scanf("%d%d",&L,&P);
	for (i=1;i<=N;i++)
	{
		S[i].d=L-S[i].d;
		Min[i]=INF;
	}
	S[++N].d=L;
	S[0].o=P;
	qsort(S+1,N,sizeof(S[0]),cmp);
	F[0][P]=1;
	Min[0]=Max[0]=P;
	for (i=0;i<MAXM;i++)
		F[N][i]=INF;
}

void dynamic()
{
	int i,j,k,l;
	for (i=0;i<N;i++)
	{
		for (j=Min[i];j<=Max[i];j++)
		{
			if (!F[i][j]) continue;
			for (k=i+1;k<=N && (l=j-(S[k].d-S[i].d))>=0;k++)
			{
				F[k][l+S[k].o]=F[i][j]+1;
				if (l+S[k].o>Max[k])
					Max[k]=l+S[k].o;
				if (l+S[k].o<Min[k])
					Min[k]=l+S[k].o;
			}
		}
	}
	for (i=Min[N];i<=Max[N];i++)
	{
		if (F[N][i]<Ans)
			Ans=F[N][i];
	}
	if (Ans==INF) Ans=1;
	Ans-=2;
}

int main()
{
	init();
	dynamic();
	cout << Ans;
	return 0;
}