int a[205],cost[205][205],f[35][205];//a保存的是rest的位置。cost保存的是i个rest与j个rest之间建一个dpot的各rest到该dpot的最短距离//f保存的是i个rest之间建j个dpot的最短距离。。。 状态方程： f[i][j]=min{f[i-1][k]+cost[k+1][j]} k=i-1.......j-1;     #include<stdio.h>#include<string.h>int a[205],cost[205][205],f[35][205];//a保存的是rest的位置。cost保存的是i个rest与j个rest之间建一个dpot的各rest到该dpot的最短距离//f保存的是i个rest之间建j个dpot的最短距离。。。int abs(int a){    if(a<0) return -a;    else return a;}int main(){    int i,j,kk,n,k,mid;    int N=0;    while(scanf("%d %d",&n,&k)!=EOF)    {        if(n==0&&k==0) break;        N++;        for(i=1;i<=n;i++)        {            scanf("%d",&a[i]);        }         memset(cost, 0, sizeof(cost));        for(i=1;i<=n;i++)        {http://acm.hdu.edu.cn/showproblem.php?pid=1227            for(j=i+1;j<=n;j++)            {                mid=(j+i)/2;            //    cost[i][j]=0;                for(kk=i;kk<=j;kk++)                {                    cost[i][j]+=abs(a[kk]-a[mid]);                }            }        }    //    f[1][1]=0;        for(i=1;i<=n;i++)        {            f[1][i]=cost[1][i];        //    f[i][i]=0;        }        for(i=2;i<=k;i++)        {            for(j=i+1;j<=n;j++)            {                f[i][j]=f[i-1][j-1];                for(kk=i-1;kk<j-1;kk++)                {                    if(f[i-1][kk]+cost[kk+1][j]<f[i][j])                        f[i][j]=f[i-1][kk]+cost[kk+1][j];                }            }        }        printf("Chain %d\n",N);        printf("Total distance sum = %d\n\n",f[k][n]);     }    return 0;}

评论