Fast Food(DP)

题意：
给你n个饭店在横坐标轴上的位置，要你在这些饭店旁边建立k个仓库，使得所有饭店到最近的仓库距离之和最短，要你输出这个值。
思路：
这个题可以认为是管道问题的扩展版本，也可以认为是矩阵链乘的变种。
定义dp[ i ] [ j ]:表示一共i个仓库在[1, j] 这些饭店的最短距离和
转移方程：dp[ i ][ j ] = min(dp[i - 1] [k - 1] + dis[ k ] [ j ]) i取值[1,k]，j取值[i , j]，k取值[i , j]。
这里用到了dis[ i ] [ j ]:表示从第i个饭店到第j个饭店最短路径和(中位数原理即可)
注意：
j不能取i + 1(j的话我觉得取i + 1应该没问题，前面i个都放仓库就是0不用再计算，但是可能会出现玄学错误，但是我们再for两次下三角等于0，然后取j = i + 1就可以了),k 不能取 i + 1(就是断开位置从i开始，至于为什么答案是显然的从i + 1开始会错过一些最优值，比如从i开始断开更优，这里开始没有考虑好。。。)
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 10;
int a[maxn],dis[maxn][maxn],dp[maxn][maxn];
void solved(){
	int ca = 1;
	int n,k;
	while(cin>>n>>k &&  (n || k)){
		memset(a,0,sizeof(a));
		for(int i = 1; i <= n; i++){
			cin>>a[i];
		}
		memset(dis,0,sizeof(dis));
		for(int i = 1; i <= n; i++){ 
			for(int j = i + 1; j <= n; j++){
				for(int k = i; k <= j; k++){
					dis[i][j] += abs(a[(i + j) / 2] - a[k]);	
				} 
			}
		}
		memset(dp,0x3f,sizeof(dp));
		for(int i = 1; i <= n; i++)dp[1][i] = dis[1][i];
		for(int i = 2; i <= k; i++){//枚举仓库数量 
			for(int j = i; j <= n; j++){//枚举区间[i,j] 
				for(int k = i; k <= j; k++){//枚举断开位置k 
					dp[i][j] = min(dp[i - 1][k - 1] + dis[k][j],dp[i][j]);
				}
			}
		}
		cout<<"Chain "<<ca++<<endl;
		cout<<"Total distance sum = "<<dp[k][n]<<endl;
		cout<<endl;
	}
}
int main(){
	solved();
	return 0;
}

总结：
这几天写题老是有点心浮气躁的，一定要冷静啊！！！