题目大意：
有v个村庄，每个村庄有各自的位置，且每个位置互不相同。现在要在村庄上设立P个邮局，使每个村庄到最近的邮局的距离之和最小。
分析：
方法一：
这是一个动态规划的问题，dp状态比较容易想到，定义状态d[i][k]表示前i个村庄，在这i个村庄中设立k个邮局时，所有村庄到这k个邮局的最小距离
状态转移方程 dp[i][j] = min( dp[k][j-1] - 在dp[k][j-1]的状态下再设第j个邮局时少花费的距离）
k = j-1...min(i,p) 注意一定是min(i,p)否则就把设立大于p个邮局的情况加进去了，样例过了，但是会WA
代码：
#include <cstdio> #include <cstring> int a[302]; int dp[302][32]; int abs(int x){return x > 0 ? x : -x;} int min(int a,int b){return (a < b)? a : b;} int post[302]; //post[i] = Σ(a[j] - a[i]) j=i+1...n int main(){ int n,m; scanf("%d%d",&n,&m); memset(dp,0x3f3f3f,sizeof(dp)); for(int i = 1;i <= n;i++) scanf("%d",&a[i]); for(int i = 1;i <= n;i++){ int temp = 0; for(int j = 1;j <= n;j++){ if(j != i) temp += abs(a[j] - a[i]); if(j > i) post[i] += a[j] - a[i]; } dp[i][1] = temp; } for(int i = 2;i <= n;i++){ for(int k = 2;k <= i && k <= m;k++){ int minT = 0x3f3f3f; //计算在dp[k][j-1]的状态下再设第j个邮局时少花费的距离 for(int j=k-1;j < i;j++){ int now = 0,pre = 0; now = post[i]; pre = post[j]; for(int p = j+1;p < i;p++){ if(a[p] + a[p] > a[i] + a[j])now += a[i] - a[p]; else now += a[p] - a[j]; } if(dp[j][k-1] + now - pre < minT){ minT = dp[j][k-1] + now - pre; } } dp[i][k] = minT; } } int ans = 0x3f3f3f; for(int i = m;i <= n;i++) ans = min(ans,dp[i][m]); printf("%d",ans); }
方法二：方法一的状态转移方程每次的计算量比较大，而且计算起来稍微有些麻烦，在机试中时间是很宝贵的，看了一篇博客的关于这道题的讲解，比方法一简单许多 博客传送门
首先它的状态含义和方法一的不一样，方法一中 dp[i][j] 考虑的是全部村庄到现在的状态花费的距离之和，其实后面的距离每次算的方法都是一样的，不如提出来不放在状态中，于是：
定义状态d[i][j]表示前i个村庄，在这i个村庄中设立j个邮局的最小距离。（注意：不考虑村庄i之后的村庄）
s[i][j]表示村庄i至村庄j这几个村庄中设立一个邮局的最小距离。如果设立一个邮局，那么邮局设立在(a+b)/2这个位置是最优的。所以可以分解成以下子问题：
d[i][j]的最小值为d[k][j-1]的最小值加上s[k+1][i]，s[k+1][i]为在k+1至i这几个村庄中设立一个邮局的最小距离。
d[i][j]=min(d[i][j], d[k][j-1]+s[k+1][i])
边界条件d[i][1]=s[1][i].
s数组可做如下优化：
s[1][4]，把邮局设立在2和设立在3上距离是相同的。x2-x1+x3-x2+x4-x2与x3-x1+x3-x2+x4-x3相等。s[1][5]是把邮局设立在3上，s[1][5]=s[1][4]+x[5]-x[3]。
由此，可得出递推式：s[i][j]=s[i][j-1]+x[j]-x[(i+j)/2].
#include <iostream> #include <cstdio> using namespace std; const int INF=1e8; int x[305]; int d[305][35]; int s[305][305]; int main() { //freopen("in.txt","r",stdin); int n,p; while(~scanf("%d%d",&n,&p)) { for(int i=1;i<=n;i++) scanf("%d",&x[i]); for(int i=1;i<=n;i++) for(int j=1;j<i && j<=p;j++) d[i][j]=INF; for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) s[i][j]=s[i][j-1]+x[j]-x[(i+j)/2]; d[i][1]=s[1][i]; } for(int i=2;i<=n;i++) for(int j=2;j<=i && j<=p;j++) for(int k=j-1;k<i;k++) d[i][j]=min(d[i][j],d[k][j-1]+s[k+1][i]); printf("%d ",d[n][p]); } return 0; }
总结
在思考问题，写状态方程时要力求简洁，公式化，当状态方程比较繁琐的时候，会增加写代码的难度——也就意味着花费更多的时间（写和调试的时间）。并且最开始我写方法一的代码超时了，经过修改后才AC的。