2431.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"algorithm"
const int size=10010;

struct stop
{
	int f,x;
}p[size];
int n,l,h;

bool cmp(stop a,stop b)
{
	return a.x>b.x;
}

void init()
{
	int i;

	cin>>n;
	for(i=0;i<n;i++)
	{
		cin>>p[i].x>>p[i].f;
	}
	cin>>l>>h;
	
	p[n+1].x=l;p[n+1].f=0;
	p[n].x=0;p[n].f=0;
	n+=2;
	std::sort(p,p+n,cmp);
	
	if(p[0].x!=l)
		while(1)
			cout<<"faint"<<endl;
}

int mem[2][size],down;
int *best=mem[0],*temp=mem[1];

void doit()
{
	int i,j,t;
	
	down=0;
	
	best[0]=h;
	for(i=1;i<n;i++)
	{
		for(j=down;j<=i;j++)
			temp[j]=-1;
		for(j=down;j<=i;j++)
		{
			if(j<i&&best[j]-(p[i-1].x-p[i].x)>temp[j])
				temp[j]=best[j]-(p[i-1].x-p[i].x);
			
			if(j>down && (t=best[j-1]-(p[i-1].x-p[i].x))>=0 && (t+=p[i].f) >temp[j])
				temp[j]=t;
			
			if(temp[j]<0)
				down=j+1;
		}
		std::swap(best,temp);
	}
}

int main()
{
	int i;
	init();
	doit();

	for(i=down;i<n-1;i++)
		if(best[i]>=0)break;
	if(i<n-1)
		cout<<i<<endl;
	else cout<<-1<<endl;

	return 0;
}