> #include<stdio.h>
> #define Size 200
> 
> int point[Size+1];
> int sum[Size+1];
> int edge[Size+1];
> 
> int array[Size+1][Size+1];       ///////////  att!!!!!
> 
> void prejudge(int total)
> {     
>      int i = 0;
> 	 sum[0]=edge[0];
> 	 for(i=1;i<=total;i++)
> 		 sum[i]=sum[i-1]+point[i]+edge[i];
> }
> void DP(int total)
> {
>     int start,step,mid;
> 	int final;
> 	int i;
> 	for(i=1;i<=total;i++)
> 		array[i][i]=sum[i]-sum[i-1]+edge[i-1];
> 	for(step=1;step<total;step++)
> 		for(start=1;start+step<=total;start++)
> 		{  
> 		   final=start+step;
>            array[start][final]=array[start+1][final];
> 		   for(mid=start+1;mid<=final;mid++)
> 			   if(array[start][final] > array[start][mid-1]+array[mid+1][final])
> 				   array[start][final]=array[start][mid-1]+array[mid+1][final];
> 		  array[start][final]+=sum[final]-sum[start-1]+edge[start-1];
> 		}
> 	printf("%d\n",array[1][total]);
> 
> }
> int main()
> {
>    int total;
>    int i,j;
>    while(scanf("%d",&total)!=EOF &&total!=0)
>    {
> 	   for(i=1;i<=total;i++)
> 		   scanf("%d",point+i);
> 	   for(i=0;i<=total;i++)
> 		   scanf("%d",edge+i);
> 	   for(i=0;i<=total;i++)
> 		   for(j=0;j<=total;j++)
> 		     array[i][j]=0;
> 	   prejudge(total);
> 	   DP(total);
>    }
>    return 0;
> }

• Re:那估计你程序还是有问题，碰巧过了而已 (29) huster 2004-09-26 05:47:14