> #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);
> 	}
> }
> 

• 恩,我代码实现能力不强,这我都考虑了....然后有写了个避免一点有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