LintCode: Post Office Problem
http://poj.org/problem?id=1160
X. O(N^3)
https://zhengyang2015.gitbooks.io/lintcode/post_office_problem_435.html
存在一堆有用的研究.
TODO: https://github.com/kamyu104/LintCode/blob/master/C++/post-office-problem.cpp
http://www.cnblogs.com/tonix/p/4971601.html
https://www.slideshare.net/awebneck/the-post-office-problem
Read full article from LintCode: Post Office Problem
http://poj.org/problem?id=1160
On one line there are n houses. Give you an array of integer means the the position of each house. Now you need to pick k position to build k post office, so that the sum distance of each house to the nearest post office is the smallest. Return the least possible sum of all distances between each village and its nearest post office.
Example
Example
Given array a =
[1,2,3,4,5], k = 2. return 3.
Challenge
Could you solve this problem in
O(n^2) time ?
X.
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=137654&page=2
这种matrix叫做monge matrix.
存在一堆有用的研究.
https://blog.csdn.net/find_my_dream/article/details/4931222
四边形不等式优化动态规划原理:
1.当决策代价函数w[i][j]满足w[i][j]+w[i’][j’]<=w[I;][j]+w[i][j’](i<=i’<=j<=j’)时,称w满足四边形不等式.当函数w[i][j]满足w[i’][j]<=w[i][j’] i<=i’<=j<=j’)时,称w关于区间包含关系单调.
2.如果状态转移方程m为且决策代价w满足四边形不等式的单调函数(可以推导出m亦为满足四边形不等式的单调函数),则可利用四边形不等式推出最优决策s的单调函数性,从而减少每个状态的状态数,将算法的时间复杂度由原来的O(n^3)降低为O(n^2).方法是通过记录子区间的最优决策来减少当前的决策量.令:
s[i][j]=max{k | ma[i][j] = m[i][k-1] + m[k][j] + w[i][j]}
由于决策s具有单调性,因此状态转移方程可修改为:
证明过程: (转载)
设m[i,j]表示动态规划的状态量。
m[i,j]有类似如下的状态转移方程：
m[i,j]=opt{m[i,k]+m[k,j]}(i≤k≤j)
如果对于任意的a≤b≤c≤d，有m[a,c]+m[b,d]≤m[a,d]+m[b,c]，那么m[i,j]满足四边形不等式。
以上是适用这种优化方法的必要条件
对于一道具体的题目，我们首先要证明它满足这个条件，一般来说用数学归纳法证明，根据题目的不同而不同。
通常的动态规划的复杂度是O(n3)，我们可以优化到O(n2)
设s[i,j]为m[i,j]的决策量，即m[i,j]=m[i,s[i,j]]+m[s[i,j]+j]
我们可以证明，s[i,j-1]≤s[i,j]≤s[i+1,j] （证明过程见下）
那么改变状态转移方程为：
m[i,j]=opt{m[i,k]+m[k,j]} (s[i,j-1]≤k≤s[i+1,j])
复杂度分析：不难看出，复杂度决定于s的值，以求m[i,i+L]为例，
(s[2,L+1]-s[1,L])+(s[3,L+2]-s[2,L+1])…+(s[n-L+1,n]-s[n-L,n-1])=s[n-L+1,n]-s[1,L]≤n
所以总复杂度是O(n2)
对s[i,j-1]≤s[i,j]≤s[i+1,j]的证明：
设mk[i,j]=m[i,k]+m[k,j]，s[i,j]=d
对于任意k<d，有mk[i,j]≥md[i,j]（这里以m[i,j]=min{m[i,k]+m[k,j]}为例,max的类似），接下来只要证明mk[i+1,j]≥md[i+1,j]，那么只有当s[i+1,j]≥s[i,j]时才有可能有ms[i+1,j][i+1,j]≤md[i+1,j]
(mk[i+1,j]-md[i+1,j]) - (mk[i,j]-md[i,j])
=(mk[i+1,j]+md[i,j]) - (md[i+1,j]+mk[i,j])
=(m[i+1,k]+m[k,j]+m[i,d]+m[d,j]) - (m[i+1,d]+m[d,j]+m[i,k]+m[k,j])
=(m[i+1,k]+m[i,d]) - (m[i+1,d]+m[i,k])
∵m满足四边形不等式，∴对于i<i+1≤k<d有m[i+1,k]+m[i,d]≥m[i+1,d]+m[i,k]
∴(mk[i+1,j]-md[i+1,j])≥(mk[i,j]-md[i,j])≥0
∴s[i,j]≤s[i+1,j]，同理可证s[i,j-1]≤s[i,j]
证毕
扩展：
以上所给出的状态转移方程只是一种比较一般的，其实，很多状态转移方程都满足四边形不等式优化的条件。
解决这类问题的大概步骤是：
0.证明w满足四边形不等式，这里w是m的附属量，形如m[i,j]=opt{m[i,k]+m[k,j]+w[i,j]}，此时大多要先证明w满足条件才能进一步证明m满足条件
1.证明m满足四边形不等式
2.证明s[i,j-1]≤s[i,j]≤s[i+1,j]
pku 1160 Post Office 解题报告
题意: 给出m个村庄及其距离，给出n个邮局，要求怎么建n个邮局使代价最小.
算法:很显然用到动态规划,那么假设:
d[i…n],各邮局的坐标
w[i][j]表示在d[i][j]之间建立一个邮局的村庄为k,则k为i与j之和的一半(很显然在中间建一个邮局距离最小),那么
m[i][j]为在前j个村庄建立i个邮局的最小距离和.
那么状态转移方程为:
边界条件: m[1][j]=w[1][j] (1<=j<=m)
状态转移方程:
那么思路则为:
for i=2 to p do //递推邮局数
{
//m:在前j个村庄建立i个邮局的最小距离和
for j=n dwonto i+1 do //按递减顺序枚举尾指针
m[i][j]=inf;
for k=1 to n do
{
temp = m[i-1][k]+calcw(k+1,j);
if(temp<m[i][j]) m[i][j]=temp;
}
}
这样时间复杂度显然为O(n^3),这是不能接受的.
仔细分析这dp算法,关键是决策变量k枚举数太多, 联系到四边形不等式原理,w[i][j]与m[i][j]很明显符合四边形不等式,我们假设决策变量s[i][j],如果在1到10的村庄中,建立1个邮局的最佳位置为8,那么在决定见多一个邮局的话,当然是在1到8之间了(根据四边形不等式原理猜想到),所以就在dp的过程中,用s[i][j]记录前i-1个邮局的村庄数. 那么我们第三次搜索的时候,就需要根据决策表s[i-1][j]<=k<=s[i][j+1]的范围内枚举.而可以证明s[i][j]具有单调性,那么我们就可以利用s[i][j]单调性限制了上下界然后把 O(n^3)弄成了 O(n^2)。
X. https://xizha677.gitbooks.io/codenotes/content/post-office-problem.html
https://zhengyang2015.gitbooks.io/lintcode/content/post_office_problem_435.html
https://lxming.wordpress.com/2015/07/08/post-office-problem-lintcode/
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=137654&page=2
这种matrix叫做monge matrix.
存在一堆有用的研究.
https://blog.csdn.net/find_my_dream/article/details/4931222
四边形不等式优化动态规划原理:
1.当决策代价函数w[i][j]满足w[i][j]+w[i’][j’]<=w[I;][j]+w[i][j’](i<=i’<=j<=j’)时,称w满足四边形不等式.当函数w[i][j]满足w[i’][j]<=w[i][j’] i<=i’<=j<=j’)时,称w关于区间包含关系单调.
2.如果状态转移方程m为且决策代价w满足四边形不等式的单调函数(可以推导出m亦为满足四边形不等式的单调函数),则可利用四边形不等式推出最优决策s的单调函数性,从而减少每个状态的状态数,将算法的时间复杂度由原来的O(n^3)降低为O(n^2).方法是通过记录子区间的最优决策来减少当前的决策量.令:
s[i][j]=max{k | ma[i][j] = m[i][k-1] + m[k][j] + w[i][j]}
由于决策s具有单调性,因此状态转移方程可修改为:
证明过程: (转载)
设m[i,j]表示动态规划的状态量。
m[i,j]有类似如下的状态转移方程：
m[i,j]=opt{m[i,k]+m[k,j]}(i≤k≤j)
如果对于任意的a≤b≤c≤d，有m[a,c]+m[b,d]≤m[a,d]+m[b,c]，那么m[i,j]满足四边形不等式。
以上是适用这种优化方法的必要条件
对于一道具体的题目，我们首先要证明它满足这个条件，一般来说用数学归纳法证明，根据题目的不同而不同。
通常的动态规划的复杂度是O(n3)，我们可以优化到O(n2)
设s[i,j]为m[i,j]的决策量，即m[i,j]=m[i,s[i,j]]+m[s[i,j]+j]
我们可以证明，s[i,j-1]≤s[i,j]≤s[i+1,j] （证明过程见下）
那么改变状态转移方程为：
m[i,j]=opt{m[i,k]+m[k,j]} (s[i,j-1]≤k≤s[i+1,j])
复杂度分析：不难看出，复杂度决定于s的值，以求m[i,i+L]为例，
(s[2,L+1]-s[1,L])+(s[3,L+2]-s[2,L+1])…+(s[n-L+1,n]-s[n-L,n-1])=s[n-L+1,n]-s[1,L]≤n
所以总复杂度是O(n2)
对s[i,j-1]≤s[i,j]≤s[i+1,j]的证明：
设mk[i,j]=m[i,k]+m[k,j]，s[i,j]=d
对于任意k<d，有mk[i,j]≥md[i,j]（这里以m[i,j]=min{m[i,k]+m[k,j]}为例,max的类似），接下来只要证明mk[i+1,j]≥md[i+1,j]，那么只有当s[i+1,j]≥s[i,j]时才有可能有ms[i+1,j][i+1,j]≤md[i+1,j]
(mk[i+1,j]-md[i+1,j]) - (mk[i,j]-md[i,j])
=(mk[i+1,j]+md[i,j]) - (md[i+1,j]+mk[i,j])
=(m[i+1,k]+m[k,j]+m[i,d]+m[d,j]) - (m[i+1,d]+m[d,j]+m[i,k]+m[k,j])
=(m[i+1,k]+m[i,d]) - (m[i+1,d]+m[i,k])
∵m满足四边形不等式，∴对于i<i+1≤k<d有m[i+1,k]+m[i,d]≥m[i+1,d]+m[i,k]
∴(mk[i+1,j]-md[i+1,j])≥(mk[i,j]-md[i,j])≥0
∴s[i,j]≤s[i+1,j]，同理可证s[i,j-1]≤s[i,j]
证毕
扩展：
以上所给出的状态转移方程只是一种比较一般的，其实，很多状态转移方程都满足四边形不等式优化的条件。
解决这类问题的大概步骤是：
0.证明w满足四边形不等式，这里w是m的附属量，形如m[i,j]=opt{m[i,k]+m[k,j]+w[i,j]}，此时大多要先证明w满足条件才能进一步证明m满足条件
1.证明m满足四边形不等式
2.证明s[i,j-1]≤s[i,j]≤s[i+1,j]
pku 1160 Post Office 解题报告
题意: 给出m个村庄及其距离，给出n个邮局，要求怎么建n个邮局使代价最小.
算法:很显然用到动态规划,那么假设:
d[i…n],各邮局的坐标
w[i][j]表示在d[i][j]之间建立一个邮局的村庄为k,则k为i与j之和的一半(很显然在中间建一个邮局距离最小),那么
m[i][j]为在前j个村庄建立i个邮局的最小距离和.
那么状态转移方程为:
边界条件: m[1][j]=w[1][j] (1<=j<=m)
状态转移方程:
那么思路则为:
for i=2 to p do //递推邮局数
{
//m:在前j个村庄建立i个邮局的最小距离和
for j=n dwonto i+1 do //按递减顺序枚举尾指针
m[i][j]=inf;
for k=1 to n do
{
temp = m[i-1][k]+calcw(k+1,j);
if(temp<m[i][j]) m[i][j]=temp;
}
}
这样时间复杂度显然为O(n^3),这是不能接受的.
仔细分析这dp算法,关键是决策变量k枚举数太多, 联系到四边形不等式原理,w[i][j]与m[i][j]很明显符合四边形不等式,我们假设决策变量s[i][j],如果在1到10的村庄中,建立1个邮局的最佳位置为8,那么在决定见多一个邮局的话,当然是在1到8之间了(根据四边形不等式原理猜想到),所以就在dp的过程中,用s[i][j]记录前i-1个邮局的村庄数. 那么我们第三次搜索的时候,就需要根据决策表s[i-1][j]<=k<=s[i][j+1]的范围内枚举.而可以证明s[i][j]具有单调性,那么我们就可以利用s[i][j]单调性限制了上下界然后把 O(n^3)弄成了 O(n^2)。
X. https://xizha677.gitbooks.io/codenotes/content/post-office-problem.html
In above example, we could easily see that a post office need to be built at 3 when k = 1. This means if there is only one post office, this office should always be built at the center of the sorted array to provide the least sum of all distances.
Therefore, we could pre-calculate all the least sum of all distances for villages from i to j with only one post office. Once we find all the distances, we could use f[n][k] to represent the total distance for array with n length and k post offices. The state function could be defined as:
f[i][l] = Math.min(f[i][l], f[j][l - 1] + dist[j + 1][i]), where j from 0 to i - 1
This formula indicates that we would like to find the minimal split between the range 0 - i. In the second parameter of Math.min, we have cut finding l post office in range 0 - i to two parts:
- Find l - 1 post office in range 0 - j
- Find 1 post office in range j - i
https://zhengyang2015.gitbooks.io/lintcode/content/post_office_problem_435.html
https://lxming.wordpress.com/2015/07/08/post-office-problem-lintcode/
This is a DP problem. We also need to pre-calculate the cost between any two points with a single post office. The DP formula is:
i: the number of post office
j: the jth house.
dp[i][j]: the minimal cost of having i post offices in houses [0]-[j]
cost[i][j]: the minimal cost of building a post office between i and j (inclusive).
dp[i][j] = Math.min(dp[i][j], dp[i – 1][l-1] + cost[l][j]);
我們可以利用動態規劃來幫助我們解這題，網友 find_my_dream 提供了以下思路：
dis[i][j] 表示在第i個村莊與第j個房子中間造一間郵局的情況下，所有村莊到郵局的距離和
計算dis[i][j]的方式：
- 先求得i 與 j 的中點 mid = (i + j) / 2
- 接著把所有i 與 j 中間所有村莊與郵局的距離加總起來即可
dp[i][l] 表示在前i個村莊建l間郵局的最小距離和
計算dp[i][l] 的方式：
- 從第 1 座村莊到第 i 座村莊找出一個切點 j 使得滿足以下條件
- 前 j 個村莊蓋 l - 1 間郵局，加上在第 j + 1 個村莊到第 i 個村莊的中間蓋一間郵局的矩離和最小。
- dp[i][l] = dp[j][l - 1] + dis[j + 1][i]
public int postOffice(int[] A, int k) {
// 如果沒有半間房，或是郵局的數量比房子多的話，直接返回0
if (A == null || A.length == 0 || k >= A.length) {
return 0;
}
int len = A.length;
Arrays.sort(A);
int[][] dp = new int[len + 1][len + 1];
int[][] dis = init(A);
// 前i間房只能蓋一間郵局的話，就不斷的把郵局蓋在前i間房的中間
for (int i = 0; i <= len; i++) {
dp[i][1] = dis[1][i];
}
//要蓋兩間房的話才有戲唱，因此從兩間房開始枚舉
for (int l = 2; l <= k; l++) {
for (int i = l; i <= len; i++) {
dp[i][l] = Integer.MAX_VALUE;
for (int j = 0; j < i; j++) {
if (dp[i][l] == Integer.MAX_VALUE || dp[i][l] > (dp[j][l - 1] + dis[j + 1][i])) {
dp[i][l] = dp[j][l - 1] + dis[j + 1][i];
}
}
}
}
return dp[len][k];
}
private int[][] init(int[] A) {
int len = A.length;
int[][] dist = new int[len + 1][len + 1];
for (int i = 1; i <= len; i++) {
for (int j = i + 1; j <= len; j++) {
int mid = (i + j) / 2;
for (int k = i; k <= j; k++) {
dist[i][j] += Math.abs(A[k - 1] - A[mid - 1]);
}
}
}
return dist;
}int [][]init(int []A) { int n = A.length; int [][]dis = new int [n+1][n+1]; for(int i = 1; i <= n; i++) { for(int j = i+1 ;j <= n;++j) { int mid = (i+j) /2; for(int k = i;k <= j;++k) dis[i][j] += Math.abs(A[k - 1] - A[mid - 1]); } } return dis; } public int postOffice(int[] A, int k) { int n = A.length; Arrays.sort(A); int [][]dis = init(A); int [][]dp = new int[n + 1][k + 1]; if(n == 0 || k >= A.length) return 0; int ans = Integer.MAX_VALUE; for(int i = 0;i <= n;++i) { dp[i][1] = dis[1][i]; } for(int nk = 2; nk <= k; nk++) { for(int i = nk; i <= n; i++) { dp[i][nk] = Integer.MAX_VALUE; for(int j = 0; j < i; j++) { if(dp[i][nk] == Integer.MAX_VALUE || dp[i][nk] > dp[j][nk-1] + dis[j+1][i]) dp[i][nk] = dp[j][nk-1] + dis[j+1][i]; } } } return dp[n][k]; }
This is a DP problem. We also need to pre-calculate the cost between any two points with a single post office. The DP formula is:
i: the number of post office
j: the jth house.
dp[i][j]: the minimal cost of having i post offices in houses [0]-[j]
cost[i][j]: the minimal cost of building a post office between i and j (inclusive).
dp[i][j] = Math.min(dp[i][j], dp[i – 1][l-1] + cost[l][j]);
public int postOffice(int[] A, int k) {
int n = A.length;
Arrays.sort(A);
int[][] dp = new int[n+1][n+1];
int[][] dis = init(A);
if(n == 0 || k >= A.length) return 0;
for(int i = 0; i <= n; i++){
dp[i][1] = dis[1][i];
}
for(int l = 2; l <= k; l++){
for(int i=l; i <= n; i++){
dp[i][l] = Integer.MAX_VALUE;
for(int j = 0; j < i; j++){
if(dp[i][l] == Integer.MAX_VALUE || dp[i][l] > (dp[j][l-1] + dis[j+1][i])){
dp[i][l] = dp[j][l-1] + dis[j+1][i];
}
}
}
}
return dp[n][k];
}
private int[][] init(int[] A){
int n = A.length;
int[][] dis = new int[n+1][n+1];
for(int i = 1; i <= n; i++){
for(int j = i+1; j <= n; j++){
int mid = (i+j)/2;
for(int k = i; k <= j; k++){
dis[i][j] += Math.abs(A[k-1] - A[mid-1]);
}
}
}
return dis;
}
https://github.com/kamyu104/LintCode/blob/master/C++/post-office-problem.cpp| int postOffice(vector<int>& A, int k) { const int n = A.size(); | |
| if (A.empty() || k >= n) { | |
| return 0; | |
| } | |
| sort(A.begin(), A.end()); // Time: O(nlogn) | |
| // Precompute cost. | |
| // Time: O(n^3) | |
| // Space: O(n^2) | |
| vector<vector<int>> cost(A.size() + 1, vector<int>(A.size() + 1, 0)); | |
| computeMinCost(A, &cost); | |
| // DP of sum. | |
| // Time: O(k * n^2) | |
| // Space: O(k * n) | |
| // sum[i][j] denotes the smallest sum of | |
| // picking i post offices for the first j houses. | |
| vector<vector<int>> sum(k + 1, vector<int>(A.size() + 1, INT_MAX)); | |
| sum[0][0] = 0; | |
| for (int i = 1; i <= k; ++i) { | |
| for (int j = 0; j < n; ++j) { | |
| if (sum[i - 1][j] != INT_MAX) { | |
| for (int r = 1; j + r <= n; ++r) { | |
| sum[i][j + r] = min(sum[i][j + r], | |
| sum[i - 1][j] + cost[j + 1][j + r]); | |
| } | |
| } | |
| } | |
| } | |
| return sum[k][n]; | |
| } | |
| void computeMinCost(const vector<int>& A, vector<vector<int>> *cost) { | |
| // Min cost of building a post office between house (i, j). | |
| // This post office must be in median position. | |
| const int n = A.size(); | |
| for (int i = 0; i < n; ++i) { | |
| for (int j = i; j < n; ++j) { | |
| int mid = (i + j) / 2; | |
| for (int r = i; r <= mid; ++r) { | |
| (*cost)[i + 1][j + 1] += A[mid] - A[r]; | |
| } | |
| for (int r = mid + 1; r <= j; ++r) { | |
| (*cost)[i + 1][j + 1] += A[r] - A[mid]; | |
| } | |
| } | |
| } | |
| } |
https://zhengyang2015.gitbooks.io/lintcode/post_office_problem_435.html
状态函数：
dp[i][l]＝dp[j][l-1] + dis[j+1][i] (l-1<=j<i)。
其中dp[i][l]表示在前i个村庄中建l个post的最短距离，j为分隔点，可以将问题转化为在前j个村庄建l－1个post的最短距离＋在第j＋1到第i个村庄建1个post的最短距离。其中有个性质，如元素是单调排列的，则在中间位置到各个元素的距离和最小。
- 初始化dis矩阵，枚举不同开头和结尾的村庄之间建1个post的最小距离，即求出开头和结尾村庄的中间点，然后计算开头到结尾的所有点到中间点的距离。记得要对原矩阵排序，这样才能用中间点距离最小性质。
- 初始化dp矩阵，即初始化dp[i][1]，求前i个村庄建1个post的最小距离（可根据dis求出）。
- post数l从2枚举到k，开始村庄i从l枚举到结尾（因为要建l个post至少需要l个村庄，否则没有意义），然后根据状态函数求dp[i][l]，分割点j从l－1枚举到i-1（前j个村庄建l－1个post则至少需要l－1个村庄），在这些分隔点的情况下求dp[i][l]的最小值。
4.返回dp[n][k]即可
private int[][] initial(int[] A){
int n = A.length;
int[][] dis = new int[n + 1][n + 1];
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
int mid = (i + j) / 2;
for(int k = i; k <= j; k++){
//所有点到mid的距离
dis[i][j] += Math.abs(A[k - 1] - A[mid - 1]);
}
}
}
return dis;
}
public int postOffice(int[] A, int k) {
// Write your code here
if(A == null || A.length == 0 || k <= 0 || k >= A.length){
return 0;
}
//一个Array只有单调才满足中间的数和其它所有数的差的绝对值之和最小
Arrays.sort(A);
int n = A.length;
//dis[i][j]: the distance sum if build post in the mid of the i,j
int[][] dis = initial(A);
//dp[i][l]: 前i个house建l个post的最小距离
int[][] dp = new int[n + 1][k + 1];
//只建一个post情况，在中间建距离之和最小
for(int i = 0; i <= n; i++){
dp[i][1] = dis[1][i];
}
for(int l = 2; l <= k; l++){
for(int i = l; i <= n; i++){
dp[i][l] = Integer.MAX_VALUE;
//j为分割点，从l-1到i-1(因为l－1个post至少需要l－1个house)
for(int j = l - 1; j < i; j++){
dp[i][l] = Math.min(dp[i][l], dp[j][l - 1] + dis[j + 1][i]);
}
}
}
return dp[n][k];
}
先说朴素的dp方程：
f[i][j]表示前j个村庄建i个邮局的最小代价。
w[i][j]表示i到j之间建一个邮局的最小代价（显然是建在中间代价最小）
f[i][j]=min(f[i-1][k]+w[k+1][j])
这样转移是O(n^3)的。
O(N^2*k)- int w[305][305],f[305][305],s[305][305],n,m,p[305];
- void Getw()
- {
- for (int i=1;i<=n;i++)
- {
- w[i][i]=0;
- for (int j=i+1;j<=n;j++)
- w[i][j]=w[i][j-1]+p[j]-p[(i+j)>>1];
- }
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for (int i=1;i<=n;i++)
- scanf("%d",&p[i]);
- Getw();
- memset(f,127,sizeof(f));
- for (int i=1;i<=n;i++)
- f[1][i]=w[1][i],s[1][i]=0;
- for (int i=2;i<=m;i++)
- {
- s[i][n+1]=n;
- for (int j=n;j>=i;j--)
- for (int k=s[i-1][j];k<=s[i][j+1];k++)
- if (f[i-1][k]+w[k+1][j]<f[i][j])
- s[i][j]=k,f[i][j]=f[i-1][k]+w[k+1][j];
- }
- printf("%d\n",f[m][n]);
- return 0;
- }
四边形不等式优化动态规划原理:
1.当决策代价函数w[i][j]满足w[i][j]+w[i’][j’]<=w[I;][j]+w[i][j’](i<=i’<=j<=j’)时,称w满足四边形不等式.当函数w[i][j]满足w[i’][j]<=w[i][j’] i<=i’<=j<=j’)时,称w关于区间包含关系单调.
2.如果状态转移方程m为
且决策代价w满足四边形不等式的单调函数(可以推导出m亦为满足四边形不等式的单调函数),则可利用四边形不等式推出最优决策s的单调函数性,从而减少每个状态的状态数,将算法的时间复杂度由原来的O(n^3)降低为O(n^2).方法是通过记录子区间的最优决策来减少当前的决策量.令:
且决策代价w满足四边形不等式的单调函数(可以推导出m亦为满足四边形不等式的单调函数),则可利用四边形不等式推出最优决策s的单调函数性,从而减少每个状态的状态数,将算法的时间复杂度由原来的O(n^3)降低为O(n^2).方法是通过记录子区间的最优决策来减少当前的决策量.令:
s[i][j]=max{k | ma[i][j] = m[i][k-1] + m[k][j] + w[i][j]}
由于决策s具有单调性,因此状态转移方程可修改为:
证明过程: (转载)
设m[i,j]表示动态规划的状态量。
m[i,j]有类似如下的状态转移方程：
m[i,j]=opt{m[i,k]+m[k,j]}(i≤k≤j)
如果对于任意的a≤b≤c≤d，有m[a,c]+m[b,d]≤m[a,d]+m[b,c]，那么m[i,j]满足四边形不等式。
以上是适用这种优化方法的必要条件
对于一道具体的题目，我们首先要证明它满足这个条件，一般来说用数学归纳法证明，根据题目的不同而不同。
通常的动态规划的复杂度是O(n3)，我们可以优化到O(n2)
设s[i,j]为m[i,j]的决策量，即m[i,j]=m[i,s[i,j]]+m[s[i,j]+j]
我们可以证明，s[i,j-1]≤s[i,j]≤s[i+1,j] （证明过程见下）
那么改变状态转移方程为：
m[i,j]=opt{m[i,k]+m[k,j]} (s[i,j-1]≤k≤s[i+1,j])
复杂度分析：不难看出，复杂度决定于s的值，以求m[i,i+L]为例，
(s[2,L+1]-s[1,L])+(s[3,L+2]-s[2,L+1])…+(s[n-L+1,n]-s[n-L,n-1])=s[n-L+1,n]-s[1,L]≤n
所以总复杂度是O(n2)
对s[i,j-1]≤s[i,j]≤s[i+1,j]的证明：
设mk[i,j]=m[i,k]+m[k,j]，s[i,j]=d
对于任意k<d，有mk[i,j]≥md[i,j]（这里以m[i,j]=min{m[i,k]+m[k,j]}为例,max的类似），接下来只要证明mk[i+1,j]≥md[i+1,j]，那么只有当s[i+1,j]≥s[i,j]时才有可能有ms[i+1,j][i+1,j]≤md[i+1,j]
(mk[i+1,j]-md[i+1,j]) - (mk[i,j]-md[i,j])
=(mk[i+1,j]+md[i,j]) - (md[i+1,j]+mk[i,j])
=(m[i+1,k]+m[k,j]+m[i,d]+m[d,j]) - (m[i+1,d]+m[d,j]+m[i,k]+m[k,j])
=(m[i+1,k]+m[i,d]) - (m[i+1,d]+m[i,k])
∵m满足四边形不等式，∴对于i<i+1≤k<d有m[i+1,k]+m[i,d]≥m[i+1,d]+m[i,k]
∴(mk[i+1,j]-md[i+1,j])≥(mk[i,j]-md[i,j])≥0
∴s[i,j]≤s[i+1,j]，同理可证s[i,j-1]≤s[i,j]
证毕
扩展：
以上所给出的状态转移方程只是一种比较一般的，其实，很多状态转移方程都满足四边形不等式优化的条件。
解决这类问题的大概步骤是：
0.证明w满足四边形不等式，这里w是m的附属量，形如m[i,j]=opt{m[i,k]+m[k,j]+w[i,j]}，此时大多要先证明w满足条件才能进一步证明m满足条件
1.证明m满足四边形不等式
2.证明s[i,j-1]≤s[i,j]≤s[i+1,j]
pku 1160 Post Office 解题报告
题意: 给出m个村庄及其距离，给出n个邮局，要求怎么建n个邮局使代价最小.
算法:很显然用到动态规划,那么假设:
d[i…n],各邮局的坐标
w[i][j]表示在d[i][j]之间建立一个邮局的村庄为k,则k为i与j之和的一半(很显然在中间建一个邮局距离最小),那么
m[i][j]为在前j个村庄建立i个邮局的最小距离和.
那么状态转移方程为:
边界条件: m[1][j]=w[1][j] (1<=j<=m)
状态转移方程:
那么思路则为:
for i=2 to p do //递推邮局数
{
//m:在前j个村庄建立i个邮局的最小距离和
for j=n dwonto i+1 do //按递减顺序枚举尾指针
m[i][j]=inf;
for k=1 to n do
{
temp = m[i-1][k]+calcw(k+1,j);
if(temp<m[i][j]) m[i][j]=temp;
}
}
这样时间复杂度显然为O(n^3),这是不能接受的.
仔细分析这dp算法,关键是决策变量k枚举数太多, 联系到四边形不等式原理,w[i][j]与m[i][j]很明显符合四边形不等式,我们假设决策变量s[i][j],如果在1到10的村庄中,建立1个邮局的最佳位置为8,那么在决定见多一个邮局的话,当然是在1到8之间了(根据四边形不等式原理猜想到),所以就在dp的过程中,用s[i][j]记录前i-1个邮局的村庄数. 那么我们第三次搜索的时候,就需要根据决策表s[i-1][j]<=k<=s[i][j+1]的范围内枚举.而可以证明s[i][j]具有单调性,那么我们就可以利用s[i][j]单调性限制了上下界然后把 O(n^3)弄成了 O(n^2)。
以sample为例:
状态方程m:
决策表s:
那么状态转移方程为:
边界条件: m[1][j]=w[1][j] (1<=j<=m)
边界条件: m[1][j]=w[1][j] (1<=j<=m)
状态转移方程: 
决策记录表: s[i][j]=k
AC代码:
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 305 //村庄数的上限
#define inf 1000000000 //无穷大
long coordinate[M]; //每个村庄的x坐标
long dp[M][M]; //dp[i][j]表在在前j个村庄建立i个邮局的最小距离和为dp[i][j];
long s[M][M]; //由s[i][j]记录使用前i-1个邮局的村庄数
long euclidean[M][M]; //村庄i与村庄j间的欧式距离为euclidean[i][j]=euclidean[i][j-1]+|coordinate[j]-coordinate[i]|
long n, p, answer;
int Calculation(long i, long j)
{
long k;
//可以证明,当仅建立一个邮局时,最优解出现在中位数
k = (i + j) / 2;
return euclidean[k][j] - euclidean[k][i - 1];
}
int main()
{
//freopen("1.txt", "r", stdin);
int i, j, k;
scanf("%ld%ld", &n, &p);
for (i = 1; i <= n; i++)
{
scanf("%ld", &coordinate[i]);
}
memset(euclidean, 0, sizeof(euclidean));
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
euclidean[i][j] = euclidean[i][j - 1] + abs(coordinate[j] - coordinate[i]);
}
}
memset(dp, 0, sizeof(dp));
for (i = 1; i <= n; i++)
{
//计算在前i个村庄建立1个邮局的最小距离和
dp[1][i] = Calculation(1, i);
}
for (i = 1; i <= n; i++)
{
//每个村庄建立一个邮局
s[i][i] = i - 1;
}
for (i = 2; i <= p; i++)
{
j = n;
dp[i][j] = inf;
/*在s[i-1][j]到j-1的范围内枚举k值,计算前k个村庄建立一个i-1个邮局、第k+1个村庄~第j个村庄建立一个
邮局的距离和.若该距离为目前最小,则记下方案.*/
//由于决策量s[i][j]的最大值并不包含j=n的情况,所以这里在进行一次dp
for (k = s[i - 1][j]; k <= j - 1; k++)
{
int temp = dp[i - 1][k] + Calculation(k + 1, j);
if (temp < dp[i][j])
{
dp[i][j] = temp;
s[i][j] = k;
}
}
//按递减顺序枚举尾指针
//决策量s[i][j]已经是缩短了搜索的范围
for (j = n - 1; j >= i + 1; j--)
{
dp[i][j] = inf;
/*在s[i-1][j]到s[i][j+1]的范围内枚举k值,计算前k个村庄建立一个i-1个邮局、第k+1个村庄~第j个村庄建立一个
邮局的距离和.若该距离为目前最小,则记下方案.*/
for (k = s[i - 1][j]; k <= s[i][j + 1]; k++)
{
int temp = dp[i - 1][k] + Calculation(k + 1, j);
if (temp < dp[i][j])
{
dp[i][j] = temp;
s[i][j] = k;
}
}
}
}
printf("%d/n", dp[p][n]);
return 0;
}
这种matrix叫做monge matrix. 存在一堆有用的研究.
TODO: https://github.com/kamyu104/LintCode/blob/master/C++/post-office-problem.cpp
http://www.cnblogs.com/tonix/p/4971601.html
https://www.slideshare.net/awebneck/the-post-office-problem
Read full article from LintCode: Post Office Problem
