662 - Fast Food

 
描述：狀態方程p[i][j]=dp[i-1][k]+dist(k+1,j)，由於沒搞懂距離dist是怎麼計算的，以為是num[j]-num[k+1]，結果wa了一次，在狀態轉移的時候，采用一個數組sc記錄一下節點的位置 
#include <cstdio>  
#include <cstring>  
#define N 0x7fffffff;  
int num[210]; 
int dp[35][210]; 
int sc[35][210]; 
void show(int cur,int pos) 
{ 
    if(cur>1) show(cur-1,sc[cur][pos]-1); 
    printf("Depot %d at restaurant %d serves ",cur,(pos+sc[cur][pos])/2); 
    if(pos-sc[cur][pos]>0) printf("restaurants %d to %d\n",sc[cur][pos],pos); 
    else printf("restaurant %d\n",pos); 
} 
int dist(int x,int y) 
{ 
    int v=0,cur=(x+y)/2,p; 
    for(int i=x; i<=y; ++i) 
    { 
        p=(num[cur]-num[i]); 
        if(p<0) p=-p; 
        v+=p; 
    } 
    return v; 
} 
int main() 
{ 
   // freopen("in.txt","r",stdin);  
    int n,m,t=1; 
    while(scanf("%d%d",&n,&m)!=EOF) 
    { 
        if(!n&&!m) break; 
        for(int i=1; i<=n; ++i) scanf("%d",&num[i]); 
        for(int i=1; i<=n-m+1; ++i) dp[1][i]=dist(1,i),sc[1][i]=1; 
        for(int i=2; i<=m; ++i) 
            for(int j=i; j<=n-m+i; ++j) 
            { 
                dp[i][j]=N; 
                for(int k=i-1; k<j; ++k) 
                { 
                    int v=dist(k+1,j); 
                    if(dp[i][j]>dp[i-1][k]+v) 
                        dp[i][j]=dp[i-1][k]+v,sc[i][j]=k+1; 
                } 
            } 
        printf("Chain %d\n",t++); 
        show(m,n); 
        printf("Total distance sum = %d\n\n",dp[m][n]); 
    } 
}