//一条直线上有n个饭店，问建造k个原料厂（仍旧在商店位置）得到的最小距离//首先预处理从i到j的最小距离，可以知道选的点必为(i+j)/2,所以用dis[i][j]记录距离//dp[i][j]表示前j个建造了i个原料厂的最小距离， //状态转移：dp[i][j]从min(dp[i-1][m])(i-1<=m<=j-1)转移过来，因为//需要建厂的位置可选在i~j，故有此转移方程，需要将dp[i][j]初始化为inf，并且先处理dp[1][i]=dis[1][i] #include<cstdio>#include<cstring>#include<algorithm>using namespace std;int cas,n,k,loc[220],dis[220][220],dp[31][201];int main(){    while(scanf("%d %d",&n,&k),n&&k)    {        for(int i=1;i<=n;++i) scanf("%d",loc+i);        //若在i到j之间建原料站，则产生的距离dis[i][j]         for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)        {            dis[i][j]=0;            for(int p=i;p<=j;++p) dis[i][j]+=abs(loc[p]-loc[(i+j)>>1]);        }        for(int i=1;i<=n;++i) dp[1][i]=dis[1][i];        for(int i=2;i<=k;++i)for(int j=i;j<=n;++j)        {            dp[i][j]=0x3f3f3f3f;            for(int m=i-1;m<j;++m)             dp[i][j]=min(dp[i][j],dp[i-1][m]+dis[m+1][j]);        }        printf("Chain %d\nTotal distance sum = %d\n\n",++cas,dp[k][n]);    }}