邮局问题 vijos1242(和以前的pku上的应该是一样的.)
/*
动态规划。
将n个村庄按坐标递增依次编号为1，2，……，n，各个邮局的坐标为a[1..n]，
状态表示描述为：f[i,j]表示在前i个村庄建立j个邮局的最小距离和。所以，f[n,p]即为问题的解，
且状态转移方程和边界条件为：
f[j,1]=w[1,j];
f[i,j]=min{f[k,j - 1]+w[k+1,i]}; (i≤j, j - 1≤k≤i)
其中w[i,j]表示在a[i..j]之间建立一个邮局的最小距离和，可以证明，当仅建立一个邮局时，
最优解出现在中位数，于是，我们有：
w[i,j]=w[i,j]+|a[k]-a[t]| (1<=i
#include
#include
#include
#define min(a,b) a