#include<cstdio>
int a[200][200],n,m,xx[200],b[200][2];
unsigned char path[200][30];
void dfs(int cnt,int l)
{
	if(cnt!=0) dfs(cnt-1,path[l][cnt]-1);
	if(path[l][cnt]!=l)
		printf("Depot %d at restaurant %d serves restaurants %d to %d\n",cnt+1,((l+path[l][cnt]+1)>>1)+1,path[l][cnt]+1,l+1);
	else
		printf("Depot %d at restaurant %d serves restaurants %d\n",cnt+1,l+1,l+1);
}
int main()
{
	int i,j,k,n,m,mid,cas=1,c;
	while(scanf("%d%d",&n,&m)&&n)
	{
		for(i=0;i<n;i++) scanf("%d",xx+i);
		for(i=0;i<n-1;i++)
		{
			for(j=i+1;j<n;j++)
			{
				mid=(i+j)>>1;
				a[i][j]=0;
				for(k=i;k<mid;k++) a[i][j]+=xx[mid]-xx[k];
				for(k=mid+1;k<=j;k++) a[i][j]+=xx[k]-xx[mid];
			}
		}
		for(i=0;i<n;i++) {b[i][0]=a[0][i]; path[i][0]=0;}
		c=0;
		for(i=1;i<m;i++)
		{
			c=!c;
			for(j=i;j<n;j++)
			{
				b[j][c]=b[j-1][!c]; path[j][i]=j;
				for(k=i-1;k<j;k++)
				{
					if(b[k][!c]+a[k+1][j]<b[j][c])
					{
						b[j][c]=b[k][!c]+a[k+1][j];
						path[j][i]=k+1;
					}
				}
			}
		}
		printf("Chain %d\n",cas++);
		dfs(m-1,n-1);
		printf("Total distance sum = %d\n\n",b[n-1][c]);
	}
}
我用这个程序生成的答案，和官方的数据几乎一样，总的距离都是一样的，路径只有3条不一样，而这3条我自己看了1下好像是多解，请管理员帮忙看下，到底是哪里WA了，谢谢：）

• Re:一直WA，管理员请进1下^ ^ (51) cangratul 2007-08-01 13:44:19