PersonalCorpus 版 (精华区)

40624 2002-10-11 10:10:51 Accepted
1196 C++ 00:01.29 412K Big Guava


int main()
{
#ifndef ONLINE_JUDGE
    freopen("c:\\0acm\\zju\\i1196","r",stdin);
    freopen("c:\\0acm\\zju\\o1196","w",stdout);
#endif

    int i,j,k,l,n,m,best,now,t=0;
    int dp[200][31];
    int p[200];

    while (1) {
        scanf("%d%d\n",&n,&m);
        if ((n==0)&&(m==0)) break; else t++;
        memset(dp,0,sizeof(dp));
        for (i=0;i<n;i++) scanf("%d\n",&p[i]);
        for (i=0;i<n;i++) for (j=0;j<i;j++) dp[i][1]+=abs(p[j]-p[i]);
        for (i=1;i<n;i++) for (j=2;(j<=i+1)&&(j<=m);j++) {
            best=100000000;
            for (k=j-2;k<i;k++) {
                now=dp[k][j-1];
                for (l=k+1;l<i;l++)
                    if (abs(p[l]-p[k])>abs(p[l]-p[i])) 
now+=abs(p[l]-p[i]);
                        else now+=abs(p[l]-p[k]);
                if (now<best) best=now;
            }
            dp[i][j]=best;
        }
        for (i=m-1;i<n;i++) for (j=i+1;j<n;j++) 
dp[i][m]+=abs(p[j]-p[i]);
        best=100000000;
        for (i=m-1;i<n;i++) if (dp[i][m]<best) best=dp[i][m];
        printf("Chain %d\n",t);
        printf("Total distance sum = %d\n\n",best);
    }

}