转载：
在n个商店中建m个仓库，使各个商店到仓库的路程之和最小，商店到哪个仓库是有选择的， 总之路程之和要最小！ 我还以给的例子来说，这道题的具体思路： 本来想做个图的，这样更清晰，我辛苦做出来的弄上面无法显示啊！我泪奔啊
- 仓库要建在商店的位置，也就是说，它一定在某个商店的坐标处； 首先： 我们可以将一下n个商店的位置存入dis[]数组（这里注意，这里说的是位置，我们可以想象，highway当做一个数轴来看，那么dis[i]就代表第i个商店在数轴上的坐标，就是位置，它不代表距离）； 然后： 我们要算出从第i个商店到第j个商店之间建一个仓库之后又增加的距离case[i][j]，这里要明白，从第i个商店到第j个商店建一个仓库，这个仓库所建的位置一定是dis[(i+j)/2],即建在它的中位数处，所以，这个增加值就是case[i][j]=abs(dis[k]-dis[(i+j)/2])(i<=k<=j); 接下来找dp[i][j];dp[i][j]代表前j个商店建i个仓库的最小距离； 下面就是最难理解的一步了，动态转移方程的寻找， 不好理解就在于有多个阶段，每个阶段都有多个状态，每个阶段的初始值都是不确定的，我们要把它初始为一个尽可能大的数，要找dp[i][j],首先dp[i][j]=10000000（尽可能的大）；然后找前一个状态，dp[i-1][m] 为啥是m呢？因为，上一个状态的仓库数是一定的，肯定是比该状态少1，但是商店数就是不确定的了，它最小是 i-1，最大是j-1,即m的范围就是(i-1<=m<=j-1)，找到上个状态后，再加上一个增加值，这个增加值是从m+1 到j之间建一个仓库所增加的距离，即case[m+1][j];该状态是dp[i-1][m]+case[m+1][j];那么dp[i][j]就是两值得最小，每次m的改变就会将最小的存入dp[i][j]，最后一次的更新，得到该状态的最小值； 这样，我们就找到了状态转移方程 dp[i][j]=MIN(dp[i-1][m]+case[m+1][j]),(i-1<=m<=j-1);
#include#include #include using namespace std; const int INF = 0x3f3f3f3f; int main() { int n,k; int a[210]; int cost[210][210];//cost[i][j]表示在i与j之间建仓库（在(i+j)/2处）的最小距离。 int dp[35][210];//dp[i][j]表示前j个商店建i个仓库的最小距离。 int item = 1; while(~scanf(%d %d,&n,&k)) { if(n == 0 && k == 0) break; for(int i = 1; i <= n; i++) scanf(%d,&a[i]); memset(cost,0,sizeof(cost)); for(int i = 1; i <= n-1; i++) { for(int j = i; j <= n; j++) { int mid = (i+j)/2; for(int k = i; k <= j; k++) cost[i][j] += abs(a[mid]-a[k]); //若在i与j商店之间建仓库，应建在(i+j)/2处。 } } for(int i = 1; i <= n; i++) dp[1][i] = cost[1][i];//切记初始化。 for(int i = 2; i <= k; i++) { for(int j = i; j <= n; j++) { dp[i][j] = INF; for(int m = i-1; m <= j-1; m++)//枚举建前i-1个仓库时，商店数m的范围是 i-1 <= m <= j-1. dp[i][j] = min(dp[i-1][m]+cost[m+1][j],dp[i][j]); } } printf(Chain %d ,item++); printf(Total distance sum = %d ,dp[k][n]); } return 0; }