#include <stdio.h>
#define min(x,y) ((x<y)?(x):(y))
long station[101][201];
void main()
{
	long i,j,n,p,last,dis,price,min;
	scanf("%ld",&n);
	for(i=0;i<=100;i++)
		for(j=0;j<=200;j++)
		{
			station[i][j]=-1;
		}
	p=1;
	station[0][100]=0;
	last=0;
	while(scanf("%ld %ld",&dis,&price)!=EOF)
	{
		for(i=0;i<=200;i++)
		{
			if(i+dis-last<=200&&station[p-1][i+dis-last]!=-1&&i!=0)
			{
				station[p][i]=min(station[p-1][i+dis-last],station[p][i-1]+price);
			}
			else if(i+dis-last<=200&&station[p-1][i+dis-last]!=-1&&i==0)
			{
				station[p][i]=station[p-1][i+dis-last];
			}
			else
			if(station[p][i-1]!=-1)
				station[p][i]=station[p][i-1]+price;
		}
		last=dis;
		p++;
	}
	if(last!=n)
	{
		min=-1;
		for(i=100+n-last;i<=200;i++)
		{
			if(station[p-1][i]!=-1)
			{
				if(min==-1)min=station[p-1][i];
				else if(min>station[p-1][i])min=station[p-1][i];
			}
		}
		if(min==-1)printf("Impossible\n");
		else printf("%ld\n",min);
	}
	else
	{	
		min=-1;
		for(i=100;i<=200;i++)
		{
			if(station[p-1][i]!=-1)
			{
				if(min==-1)min=station[p-1][i];
				else if(min>station[p-1][i])min=station[p-1][i];
			}
		}
		if(min==-1)printf("Impossible\n");
		else printf("%ld\n",min);
	}
}

• 好像写复杂了，注意对impossible的判断，而且我觉得起点和终点可能有加油站，这个要考虑一下，当初我就是跌在impossible的判断上了 (1380) sunmoonstar_love 2005-09-06 20:49:23
  • 恩,我代码实现能力不强,这我都考虑了....然后有写了个避免一点有N站的错误,,还是不行,,我估计是其他地方错了, (0) Essence_me 2005-09-06 20:51:15
    • 先简化一下吧，一次dp的循环就够了，那样清楚，更容易看 (0) sunmoonstar_love 2005-09-06 20:52:36
      • 好吧,,只能如此了 -_- B4 me (0) Essence_me 2005-09-06 20:53:31
        • B4_me (0) Essence_me 2005-09-06 20:53:43