Post Office（邮局）之四边形不等式优化dp

男娘i 2022-04-01 10:44 227阅读 0赞

**目录**

前言

题目

解析

四边形不等式优化

何为四边形不等式

何为区间包含单调性

四边形不等式性质

优化

参考代码（附注释）

--------------------

# 前言 #

可以说这道题我可花费了很大功夫才理解的。

其中有些小技巧也是我钻研了很久，再加上有一些同学 提醒 点拨才真正的看懂。

当然，这道题可不是一道水题，它的优化版是IOI2000的原题哦。

建议还是别跳了，都看看吧，还是挺重要的这知识 （虽然有点王婆卖瓜）。

说了许多废话，先看题吧

# 题目 #

There is a straight highway with villages alongside the highway. The highway is represented as an integer axis, and the position of each village is identified with a single integer coordinate. There are no two villages in the same position. The distance between two positions is the absolute value of the difference of their integer coordinates.   
Post offices will be built in some, but not necessarily all of the villages. A village and the post office in it have the same position. For building the post offices, their positions should be chosen so that the total sum of all distances between each village and its nearest post office is minimum.   
You are to write a program which, given the positions of the villages and the number of post offices, computes the least possible sum of all distances between each village and its nearest post office.

**Input**

Your program is to read from standard input. The first line contains two integers: the first is the number of villages V, 1 <= V <= 300, and the second is the number of post offices P, 1 <= P <= 30, P <= V. The second line contains V integers in increasing order. These V integers are the positions of the villages. For each position X it holds that 1 <= X <= 10000.

**Output**

The first line contains one integer S, which is the sum of all distances between each village and its nearest post office.

**Sample Input**

10 5
    1 2 3 6 7 9 11 22 44 50

**Sample Output**

大意也就是说有V个村庄，给了你这些村庄的坐标，要在这些村庄中找P个来当做邮局，使所有的村庄到离它们最近的邮局的距离最短，请你求出这个最短距离。（语文不好请见谅，实在不行就上翻译吧）

V的范围不超过300，P的范围不超过30。相信有许多人一看到这里就想到了两个字——打表！

确实，这道题打表是可以过的，毕竟是是十几年前的题了嘛，但是，如果只是打表的话，就体现不出这道题的真正价值了。它所想考察的其实是dp和它的优化：**四边形不等式。**

# **解析** #

## 四边形不等式优化 ##

在接下来我所普及的所有公式定理都不附解释，为了不占据太多篇幅 其实是根本不会罢了 ，有 疑问 兴趣的朋友们可以另外自己普及 百度 一下

“其证明过程十分复杂，暂且先不过多介绍”（摘自某老师原话）

### 何为四边形不等式 ###

当且仅当w(i, j) + w(i', j') <= w(i, j') +w(i', j) (i <= i' < j <= j')，可以说w是满足四边形不等式的。

很绕脑？看图吧。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70][]

但凡有一点数学基础的人应该都知道了吧，这里就不再说了。

### 何为区间包含单调性 ###

w(i', j) <= w(i, j') (i <= i' < j <= j')时，就可以说明w具有区间包含单调性。

直观来说小区间包含在大区间内，那么小区间的w值不能大于大区间的w值。

如图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 1][]

### 四边形不等式性质 ###

在平时的dp题目中，也许会碰到形如这样的转移方程：![dp\[i\]\[j\] = min \\left \\\{ dp\[k\]\[j - 1\] + w (k + 1, i) \\right \\\}][dp_i_j_ _ min _left _ dp_k_j - 1_ _ w _k _ 1_ i_ _right]。如果说**w函数既满足四边形不等式，又满足具有区间包含单调性，那么dp也就满足四边形不等式。**

令s(i, j)为dp最优时的下标k，如果说dp是满足四边形不等式的，那么s(i, j)也就有单调性，即为s(i, j) <= s(i, j + 1) <= s(i + 1, j + 1)，再经过变形后可以变成：s(i - 1, j) <= s(i, j) <= s(i, j + 1)。

## DP ##

相信有思考过的朋友们已经差不多列出转移方程了。

令 dp\[i\]\[j\] 为前i个村庄中一共已经设立了j个邮局。那么转移即为：![dp\[i\]\[j\] = min \\left \\\{dp\[k\]\[j - 1\] + w (k + 1, i) \\right \\\}][dp_i_j_ _ min _left _dp_k_j - 1_ _ w _k _ 1_ i_ _right]。其中k是枚举上一个邮局的右端点在哪个村庄，意思就是前面j - 1的邮局的花费加上从第i + 1个村庄全都到第j个邮局时的花费。

可以看到，这里i，j，k三个一循环就是![O (V^\{2\}P)][O _V_2_P]的复杂度，算一算其实并不会爆，所以可以直接用朴素dp来过这道题。但是呢这在IOI2000那个加强版上就不能过了。

因此，就需要用上上面才说的四边形不等式优化了。

### 优化 ###

可以看到上面的s(i - 1, j) <= s(i, j) <= s(i, j + 1)，也就是说k是可以从这个区间来枚举的，那么将会大大地减少时间复杂度了。

如果说当前k确实能小于dp原本的距离花费，那么就可以把k赋值给s\[i\]\[j\]。

for (int k = s[i - 1][j]; k <= s[i][j + 1]; k++){
        if (dp[i][j] > dp[k][j - 1] + w[k + 1][i]){
            dp[i][j] = dp[k][j - 1] + w[k + 1][i];
            s[i][j] = k;//更改最优决策
        }
    }

接下来就会有人问了，那么w该如何计算呢？可以看到w\[i\]\[j\]是存的从i村庄到j村庄距离花费。如果说把它在求dp的那个循环来求的话，应该是四次方的复杂度，这还怎么搞哦。

要是这个棘手的问题没有处理好的话，这个程序基本就宣告报废了，不管你在哪里怎么优化，什么O2、O3什么的，四次方在那里摆着呢。因此，这里就需要借助前缀和 & 后缀和数组了。

前缀和：

for (int i = 1; i <= v; i++){//求出1~i的所有村庄到1村庄的距离之和，即为前缀和数组
        pre[i] = pre[i - 1] + vill[i] - vill[1];
    }

后缀和：

for (int i = v; i >= 1; i--){//n~i的所有村庄到n村庄的距离之和，后缀和
        suf[i] = suf[i + 1] + vill[v] - vill[i];
    }

这里一定要搞清楚，前缀和后缀的数组是分别存的1~i的**所有**村庄到1村庄的距离**总和**，n~i的**所有**村庄到n村庄的距离**总和**。

就因为在这里我给卡了很久一直没想明白，然后后面的计算w也没有搞清楚。

通过前缀和&后缀和求出距离：

for (int i = 1; i <= v; i++)
        for (int j = 1; j <= v; j++){
            if (i == j)//w[i][j]是距离数组，相同村庄距离为0
                w[i][j] = 0;
            else{
                int mid = (i + j) / 2;//可以得知，在这个数列中，中位数是最小的
                w[i][j] = pre[j] - pre[mid] - (j - mid) * (vill[mid] - vill[1]) + suf[i] - suf[mid] - (mid - i) * (vill[v] - vill[mid]);
            }
        }

在这里最难懂的就是else里面的语句，显然易证出在数列中，**中位数**是跟彼此之间距离最短的。

那么w\[i\]\[j\]那一排何解呢？

且看图理解：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 2][]

画的很丑能懂就好哈。

可以看出i~mid的距离是等于：i~n的所有村庄的距离后缀和减去mid~n的所有村庄的距离后缀和。可是这个并不是i~mid的村庄之间距离，而是**i~mid之间的村庄到n的距离之和**，这也就解释了为什么后面还要有减去(j - mid) \* (vill\[mid\] - vill\[1\])的操作了。是因为要把这些多余的距离来专门减掉，剩下的就是i~mid的距离之和。

反之，mid~j的距离之和是用前缀和数组求出j~mid之间村庄到1村庄的距离之和，然后再来减去多余的那个部分。

当然，就是这里困了我很久很久。。。终于在hc  dalao的帮助下才搞懂的、、、

同时我感觉很疑惑的是，为什么非要用前缀和数组求后半段，后缀和数组求前半段呢？难道就不能用后缀和求后半段，前缀和求前半段？如果有大神能解释的欢迎到评论区评论，在线等挺急的。

不止这里 坑爹 很巧妙，还有个比较难想的地方：

for (int i = 1; i <= v; i++){//因为s[i - 1][j] <= s[i][j] <= s[i][j + 1]，所以i顺j逆
        for (int j = min (i, p); j >= 1; j--){
            if (!s[i - 1][j])
                s[i - 1][j] = min (i - 1, j - 1);
            if (!s[i][j + 1])
                s[i][j + 1] = max (i - 1, j - 1);
            for (int k = s[i - 1][j]; k <= s[i][j + 1]; k++){
                if (dp[i][j] > dp[k][j - 1] + w[k + 1][i]){
                    dp[i][j] = dp[k][j - 1] + w[k + 1][i];
                    s[i][j] = k;//更改最优决策
                }
            }
        }
    }

如上，为什么当s\[i -1\]\[j\]和s\[i\]\[j + 1\]没有值的时候要这么赋呢？

其实是因为当它没有赋值时就相当于以前没有讨论过这个情况，那么要讨论肯定要全面对吧，所以区间左边肯定要越左越好啊。可是右边呢？

可以看到这里可以用越右越好来解释，可是实际上，**这里可以直接赋值为i - 1**！有时间的可以自己调试看一下。我们就先不调了，直接解释：因为j是取min (i, p)，那么分两种情况：1、i <= p，则j最大就取的是i，i - 1 和 j - 1比较肯定是i - 1更大啊。2、i <= p，那么j最大是取的p，又因为i >= p了,所以i - 1 >= p - 1也就是i - 1 >= j - 1，最后也是i - 1更大。

循环方向这些因为已经写了注释了，所以我就不再讲了。需要注意的是，如果说i <= p就相当于不足p个村庄做邮局，那么最大也就是i。

## 参考代码（附注释） ##

/*
    令dp[i][j]为前i个村庄一共有j个邮局的最小距离。
    令w[i][j]为i村庄到j村庄的距离
    令s[i][j]为i到j之间的最优决策
    */
    #include <cstdio>
    #include <cstring>
    using namespace std;
    #define min(a, b) a < b ? a : b
    #define max(a, b) a > b ? a : b
    
    int v, p, vill[305], dp[305][305], pre[305], suf[305], w[305][305], s[305][305];
    
    int main (){
        scanf ("%d%d", &v, &p);
        for (int i = 1; i <= v; i++)
            scanf ("%d", &vill[i]);
        for (int i = 1; i <= v; i++){//求出1~i的所有村庄到1村庄的距离之和，即为前缀和数组
            pre[i] = pre[i - 1] + vill[i] - vill[1];
        }
        for (int i = v; i >= 1; i--){//n~i的所有村庄到n村庄的距离之和，后缀和
            suf[i] = suf[i + 1] + vill[v] - vill[i];
        }
        for (int i = 1; i <= v; i++)
            for (int j = 1; j <= v; j++){
                if (i == j)//w[i][j]是距离数组，相同村庄距离为0
                    w[i][j] = 0;
                else{
                    int mid = (i + j) / 2;//可以得知，在这个数列中，中位数是最小的
                    //w[i][j] = pre[mid] - pre[i] - (mid - i) * (vill[i] - vill[1]) + suf[mid] - suf[j] - (j - mid) * (vill[v] - vill[j]);
                    w[i][j] = pre[j] - pre[mid] - (j - mid) * (vill[mid] - vill[1]) + suf[i] - suf[mid] - (mid - i) * (vill[v] - vill[mid]);
                    //利用后缀和求前半段，前缀和求后半段。我不知道为什么用前缀和求前半段，后缀和求后半段不对，所以无奈只能改了
                }
            }
        memset (dp, 0x3f, sizeof (dp));
        dp[0][0] = dp[1][1] = 0;//边界条件
        for (int i = 1; i <= v; i++){//因为s[i - 1][j] <= s[i][j] <= s[i][j + 1]，所以i顺j逆
            for (int j = min (i, p); j >= 1; j--){
                if (!s[i - 1][j])
                    s[i - 1][j] = min (i - 1, j - 1);
                if (!s[i][j + 1])
                    s[i][j + 1] = max (i - 1, j - 1);//这里验算一下可以得出，max后会恒等于i - 1
                for (int k = s[i - 1][j]; k <= s[i][j + 1]; k++){
                    if (dp[i][j] > dp[k][j - 1] + w[k + 1][i]){
                        dp[i][j] = dp[k][j - 1] + w[k + 1][i];
                        s[i][j] = k;//更改最优决策
                    }
                }
            }
        }
        printf ("%d\n", dp[v][p]);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70]: /images/20220401/78a7e18285914f1395c1b81fccea1261.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 1]: /images/20220401/eb4dc78dad4042418e7b3fc09f576838.png
[dp_i_j_ _ min _left _ dp_k_j - 1_ _ w _k _ 1_ i_ _right]: https://private.codecogs.com/gif.latex?dp%5Bi%5D%5Bj%5D%20%3D%20min%20%5Cleft%20%5C%7B%20dp%5Bk%5D%5Bj%20-%201%5D%20&plus;%20w%20%28k%20&plus;%201%2C%20i%29%20%5Cright%20%5C%7D
[dp_i_j_ _ min _left _dp_k_j - 1_ _ w _k _ 1_ i_ _right]: https://private.codecogs.com/gif.latex?dp%5Bi%5D%5Bj%5D%20%3D%20min%20%5Cleft%20%5C%7Bdp%5Bk%5D%5Bj%20-%201%5D%20&plus;%20w%20%28k%20&plus;%201%2C%20i%29%20%5Cright%20%5C%7D
[O _V_2_P]: https://private.codecogs.com/gif.latex?O%20%28V%5E%7B2%7DP%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 2]: /images/20220401/4e1f751ac6414d6dbf3a6fa2d5e2b8c9.png