hdu 1227Fast Food

主题思想： 动态规划

首先 对于一组升序的数，选择仓库在中位数的位置能是距离最短，这种思路以前遇到过。

动态规划转移方程 ： 就是这个不好想啊。 首先题目要求的是距离。 那么就用dp表示距离，因为好多题都是这样。 另外dp[i][j] 是一般动态规划的形式，且一般下标从1 开始，那么我们这里要想明白dp[i][j] 表示什么意思。 令dp[i][j] 表示前j个商店中有i个仓库时，距离的和 dp[i][j]=min(dp[i][j],dp[i-1][k]+cost（k+1，j）) //k 为所有满足条件的数， i-1<= k<=j-1 //cost[k+1][j] 为在第 k+1 和j个商店（下标从1开始） 放置一个仓库的最小距离和 // 那么如何计算cost(i,j） //要使距离和最小，因为仓库距离升序，则，仓库建在i,j的中间位置 int cost(int i,int j){ int ans=0; int mid=(i+j)/2; for(int k=i;k<=j;k++){ ans+=abs(d[mid]-d[k]); } return ans; }

详细参考博客： http://blog.csdn.net/sr_19930829/article/details/39931649