2465.txt

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

Memory:36K  Time:0MS
Language:C++  Result:Accepted

Source 

#include"iostream.h"
inline int min(int a,int b)
{
	return a<b?a:b;
}

int dis[112],price[112];
int l,n;

void init()
{
	n=0;
	cin>>l;
	while(cin>>dis[n])
		cin>>price[n++];
	price[n]=99999999;
	dis[n]=l;
	n++;
}

int doit()
{
	int i,j,s,temp[212],p;
	int best[212];

	for(i=0;i<201;i++)
		best[i]=-1;
	best[100]=0;

	for(s=dis[0],i=0;i<n;i++)
	{
		for(j=0;j<201;j++)
			temp[j]=-1;
		for(j=s;j<201;j++)
			temp[j-s]=best[j];
		
		
		if(i<n-1)
		{
			p=-1;
			for(j=0;j<201;j++)
			{
				if(temp[j]>=0)
				{
					if(p<0||p>temp[j])
						p=temp[j];
				}

				if(p>=0&&(temp[j]<0||p<temp[j]))
					temp[j]=p;
				if(p>=0)p+=price[i];
			}
		}

		for(j=0;j<201;j++)
			best[j]=temp[j];
		s=dis[i+1]-dis[i];
	}
	
	int ans=-1;

	for(j=100;j<201;j++)
		if(best[j]>=0&&(ans<0||best[j]<ans))
			ans=best[j];
	return ans;
}

int main()
{
	int ans;
	init();
	ans=doit();
	if(ans<0)
		cout<<"Impossible"<<endl;
	else cout<<ans<<endl;

	return 0;
}