#include <cstdio> #include <cstring> #include <iostream> #include <vector> #include <algorithm> #include <cstdlib> using namespace std; #define INF 1000000000 const int maxn = 202; const int maxk = 31; int d[maxk][maxn],n,K,dist[maxn],sum[maxn][maxn];//到第i个已经选完前j个 bool vis[maxk][maxn]; int dp(int i,int j){ if(vis[i][j]) return d[i][j]; vis[i][j]=1; if(i==K-1){ return d[i][j]=sum[j+1][n]; } for(int l=j+1;n-l>=K-i-1;l++){ int num=dp(i+1,l)+sum[j+1][l]; d[i][j]= (l==j+1 ? num:min(d[i][j],num)); } return d[i][j]; } void print_ans(int i,int j){ if(i==K-1){ if(j+1<n) printf("Depot %d at restaurant %d serves restaurants %d to %d\n",i+1,((n+j+1)>>1),j+1,n); else printf("Depot %d at restaurant %d serves restaurant %d\n",i+1,((n+j+1)>>1),j+1); return ; } for(int l=j+1;n-l>=K-i-1;l++){ int num=d[i+1][l]+sum[j+1][l]; if(d[i][j]==num){ if(j+1<l) printf("Depot %d at restaurant %d serves restaurants %d to %d\n",i+1,((l+j+1)>>1),j+1,l); else printf("Depot %d at restaurant %d serves restaurant %d\n",i+1,((l+j+1)>>1),j+1); print_ans(i+1,l); break; } } } int main() { int kase=1; while(scanf("%d %d",&n,&K)==2){ if(!n&&!K) break; for(int i=1;i<=n;i++) scanf("%d",&dist[i]); for(int i=1;i<=n;i++) for(int j=i;j<=n;j++){ int zhong = (i+j)>>1; sum[i][j]=0; for(int k=i;k<=j;k++) sum[i][j]+=abs(dist[k]-dist[zhong]); } memset(vis,false,sizeof(vis)); int Sum = dp(0,0); printf("Chain %d\n",kase++); print_ans(0,0); printf("Total distance sum = %d\n\n",Sum); } }