@kaike
学了DP我依旧一脸懵逼，这题大概和资源分配问题相似。枚举f[i][j]表示前i个有j个东西。
让求距离差，两个循环去枚举区间[i....j]的距离差。用w[i][j]表示区间[i....j]的距离差，
w[i][j]就是从前一个状态w[i][j-1]加上a[j]到中点的距离。
预处理也是DP。
把每个邮局放到每个村庄里的距离就是0.f[i][i]=0;当邮局小于村庄时就不要考虑这个问题辣。
前i个村庄里只有一个邮局的话，f[i][1]的值就和前i个村庄的距离差就相等；f[i][1]=w[1][i];
最终式子为：f[i][j]=min(f[i][j],f[k][j-1]+w[k+1][j]);（j-1<=k< i）
前i个村庄里j个邮局就是 前k个村庄里j-1个邮局加上[k+1....j]的村庄里只有1个邮局。
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; const int INF=999999; int n,m,a[310],w[310][310],f[310][35]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) w[i][j]=w[i][j-1]+a[j]-a[(i+j)/2]; for(int i=1;i<=n;i++) { f[i][i]=0; f[i][1]=w[1][i]; } for(int j=2;j<=m;j++) for(int i=j+1;i<=n;i++) { f[i][j]=INF; for(int k=j-1;k<i;k++) f[i][j]=min(f[i][j],f[k][j-1]+w[k+1][i]); } cout<<f[n][m]; }
原文：http://www.cnblogs.com/Kaike/p/6307382.html
