1 //Accepted    420 KB    15 ms 2 //刚开始的时候一直在想把depot放在哪个restaurant，结果一直陷在里面，不知道该怎么转移 3 //现在我们把i到j看成一段处理，就认为i到j由一个depot供应，而与其他depot没有关系，且 4 //这个depot与其他的restaurant也没有关系，那么对于i到j这一段产生的花费就可以计算出来 5 //由cost[i][j]表示，对于i到j这一段，把depot放到(i+j)/2这个restaurant上，产生的花费最少 6 //下面就是dp了 7 //dp[i][j]表示前i个restaurant放置j个depot的最小花费 8 //dp[i][j]=min(dp[m][j-1]+cost[m+1][i])  j-1<=m<=i-1 9 //现在才看到动态规划中无后效性说的是神马。。。。10 #include <cstdio>11 #include <cstring>12 #include <iostream>13 using namespace std;14 const int imax_n = 201;15 const int imax_k = 31;16 const int inf = 100000000;17 int n,k;18 int cost[imax_n][imax_n];19 int dp[imax_n][imax_k];20 int dis[imax_n];21 22 int abs(int x)23 {24     if (x<0) x=-x;25     return x;26 }27 int min(int a,int b)28 {29     return a>b?b:a;30 }31 void getCost()32 {33     for (int i=1;i<=n;i++)34     {35         for (int j=i;j<=n;j++)36         {37             cost[i][j]=0;38             int temp_mid=(i+j)/2;39             for (int k=i;k<=j;k++)40             cost[i][j]+=abs(dis[temp_mid]-dis[k]);41         }42     }43 }44 void Dp()45 {46     for (int i=0;i<=n;i++)47     for (int j=0;j<=k;j++)48     dp[i][j]=inf;49     dp[0][0]=0;50     for (int i=1;i<=n;i++)51     {52         for (int j=1;j<=k && j<=i;j++)53         {54             for (int m=j-1;m<=i-1;m++)55             dp[i][j]=min(dp[i][j],dp[m][j-1]+cost[m+1][i]);56         }57     }58 }59 int main()60 {61     int t=0;62     while (scanf("%d%d",&n,&k),n+k)63     {64         for (int i=1;i<=n;i++)65         scanf("%d",&dis[i]);66         getCost();67         Dp();68         printf("Chain %d\n",++t);69         printf("Total distance sum = %d\n\n",dp[n][k]);70     }71     return 0;72 }