Monkey Party（NOI1995石子合并升级题）

系统管理员 2022-03-31 13:56 220阅读 0赞

**目录**

题目

解析

四边形不等式优化

化曲为直

参考代码

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

# 题目 #

Far away from our world, there is a banana forest. And many lovely monkeys live there. One day, SDH(Song Da Hou), who is the king of banana forest, decides to hold a big party to celebrate Crazy Bananas Day. But the little monkeys don't know each other, so as the king, SDH must do something.

Now there are n monkeys sitting in a circle, and each monkey has a making friends time. Also, each monkey has two neighbor. SDH wants to introduce them to each other, and the rules are:

1.every time, he can only introduce one monkey and one of this monkey's neighbor.

2.if he introduce A and B, then every monkey A already knows will know every monkey B already knows, and the total time for this introducing is the sum of the making friends time of all the monkeys A and B already knows;

3.each little monkey knows himself;

In order to begin the party and eat bananas as soon as possible, SDH want to know the mininal time he needs on introducing.

**Input**

There is several test cases. In each case, the first line is n(1 ≤ n ≤ 1000), which is the number of monkeys. The next line contains n positive integers(less than 1000), means the making friends time(in order, the first one and the last one are neighbors). The input is end of file.

**Output**

For each case, you should print a line giving the mininal time SDH needs on introducing.

**Sample Input**

8
    5 2 4 7 6 1 3 9

**Sample Output**

105

这道题的主要意思就是说有n个猴子围成一个圆，现在给你每个猴子认识一个其他猴子所需要的时间，如果说A认识了B，那么A和B的所有的朋友都会互相认识。但是只能**相邻**的两个猴子互相介绍认识，最后一只猴子的邻居是第一只猴子和倒数第二只猴子。请你求出最少的介绍认识的时间。

翻译能力不好可以自行百度

# 解析 #

这道题呢其实跟[NOI1995石子合并][NOI1995]差不多，只不过是少求了一个最大值而已。

其实吧这可以看出来是一个dp，思路也很好想：![dp\[i\]\[j\] = min\\left \\\{ dp\[i\]\[k\] + dp\[k + 1\]\[j\] + w\[i\]\[j\] \\right \\\}][dp_i_j_ _ min_left _ dp_i_k_ _ dp_k _ 1_j_ _ w_i_j_ _right]。w\[i\]\[j\]也就是说介绍i跟j的时间总和。但是如果说![i == j][i _ j]时可以看出时间代价应该是0吧（dp\[i\]\[j\] = 0），这就是边界考虑。

当然这里的w\[i\]\[j\]也可以利用前缀和数组来求出i到j的时间和。w\[i\]\[j\]就等价于sum\[j\] - sum\[i - 1\]。

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

因为上一篇已经讲过关于四边形不等式的具体一些东西了，所以这里就不再赘述。[不懂的戳这里][Link 1]

现在我就着重讲一下该如何运用不等式解这道题。首先先来看图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70][]

可以看到k是从i到j - 1的情况枚举的，至于为什么是j - 1呢？是因为在上面可以看到![dp\[i\]\[j\] = min\\left \\\{ dp\[i\]\[k\] + dp\[k + 1\]\[j\] + w\[i\]\[j\] \\right \\\}][dp_i_j_ _ min_left _ dp_i_k_ _ dp_k _ 1_j_ _ w_i_j_ _right]，那么看到dp\[k + 1\]\[j\]，如果说k = j的话k + 1肯定就超出j了，所以说只能是j - 1。

那么又为什么是从i呢？因为是有一个情况是从i到j的，如果说实际上是i到j的单纯合并本身就比其他所有的情况都要小，可是却把这个情况给舍弃了，那么就会得不到正解。

但是这样单纯考虑的话肯定是![O (n^\{3\})][O _n_3]的复杂度，绝对会超时！所以又引入了重点：**四边形不等式优化**。可以看到因为k是i ~ j - 1枚举的，那么如果说s\[i\]\[j - 1\]和s\[i + 1\]\[j\]为0的话，那么就直接赋值为i和j - 1就好了。

这时候或许会有人说了，为什么这里的s的下标跟上一篇的不一样呢？其实s的下标是没有固定的，只是因题而异罢了。因为如果说s\[i\]\[j\]是代表着i到j的最佳决策点时，那么如果说把右端点往左移一个，也就是j - 1，那么**最佳决策点肯定也会相应的往左移**（没懂的自己可以再想想，模拟一下），这个时候![s\[i\]\[j - 1\] < s\[i\]\[j\]][s_i_j - 1_ _ s_i_j]，反之则是![s\[i + 1\]\[j\] > s\[i\]\[j\]][s_i _ 1_j_ _ s_i_j]，也就是**![s\[i\]\[j - 1\] < s\[i\]\[j\] < s\[i + 1\]\[j\]][s_i_j - 1_ _ s_i_j_ _ s_i _ 1_j]**，这样子看就应该是这样了啊。

同时，因为是i + 1，j - 1，所以就应该是**i逆j顺**时，才有可能知道s\[i\]\[j - 1\]和s\[i + 1\]\[j\]的情况。

for (int i = n; i >= 1; i--){
        for (int j = i + 1; j <= n; j++){
            if (!s[i][j - 1])s[i][j - 1] = i;
            if (!s[i + 1][j])s[i + 1][j] = j - 1;
            for (int k = s[i][j - 1]; k <= s[i + 1][j]; k++){
                if (dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1] < dp[i][j]){
                    dp[i][j] = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];
                    s[i][j] = k;
                }
            }
        }
    }

## 化曲为直 ##

在上面我们已经得出了在直线的情况下dp\[i\]\[j\]应该如何求出来。但是呢，这毕竟是一个**环**。那么应该怎么把一个环变成一条直线呢？我们可以把1 ~ n - 1重新复制到末尾，也就是可以把它变成一条直线了。

不过呢，与此同时因为是把它直接复制到后面了，所以也需要考虑n种情况：1 ~ n, 2 ~ n + 1, 3 ~ n + 2……n ~ 2n - 1，来依次考虑最小情况。

## 参考代码 ##

#include <cstdio>
    #include <cstring>
    using namespace std;
    #define MAXN 1000 * 2
    #define INF 0x3f3f3f3f
    #define min(a, b) a < b ? a : b
    
    int n, tim[MAXN + 5], dp[MAXN + 5][MAXN + 5], sum[MAXN + 5], s[MAXN + 5][MAXN + 5], ans = INF;
    
    void read (int &x){
        x = 0;
        char c = getchar ();
        while (c < '0' || c > '9')
            c = getchar ();
        while (c >= '0' && c <= '9'){
            x = (x << 1) + (x << 3) + c - 48;
            c = getchar ();
        }
    }
    
    void print (int x){
        if (x / 10)
            print (x / 10);
        putchar (x % 10 + 48);
    }
    
    int main (){
        while (~ scanf ("%d", &n)){
            memset (dp, INF, sizeof (dp));
            memset (s, 0, sizeof (s));
            ans = INF;
            for (int i = 1; i <= n; i++){
                read (tim[i]);
                tim[i + n] = tim[i];
                sum[i] = sum[i - 1] + tim[i];
            }
            for (int i = n + 1; i < 2 * n; i++){
                sum[i] = sum[i - 1] + tim[i];
            }
            n = 2 * n - 1;
            for (int i = 1; i <= n; i++){
                dp[i][i] = 0;
            }
            for (int i = n; i >= 1; i--){
                for (int j = i + 1; j <= n; j++){
                    if (!s[i][j - 1])s[i][j - 1] = i;
                    if (!s[i + 1][j])s[i + 1][j] = j - 1;
                    for (int k = s[i][j - 1]; k <= s[i + 1][j]; k++){
                        if (dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1] < dp[i][j]){
                            dp[i][j] = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];
                            s[i][j] = k;
                        }
                    }
                }
            }
            n = (n + 1) >> 1;
            for (int i = 1; i <= n; i++){
                ans = min (ans, dp[i][n + i - 1]);
            }
            print (ans);
            putchar (10);
        }
    }

[NOI1995]: https://www.luogu.org/problemnew/show/P1880
[dp_i_j_ _ min_left _ dp_i_k_ _ dp_k _ 1_j_ _ w_i_j_ _right]: https://private.codecogs.com/gif.latex?dp%5Bi%5D%5Bj%5D%20%3D%20min%5Cleft%20%5C%7B%20dp%5Bi%5D%5Bk%5D%20&plus;%20dp%5Bk%20&plus;%201%5D%5Bj%5D%20&plus;%20w%5Bi%5D%5Bj%5D%20%5Cright%20%5C%7D
[i _ j]: https://private.codecogs.com/gif.latex?i%20%3D%3D%20j
[Link 1]: https://blog.csdn.net/weixin_43925239/article/details/85384573
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70]: /images/20220331/7de60e0ba2b440169c022a4fce338863.png
[O _n_3]: https://private.codecogs.com/gif.latex?O%20%28n%5E%7B3%7D%29
[s_i_j - 1_ _ s_i_j]: https://private.codecogs.com/gif.latex?s%5Bi%5D%5Bj%20-%201%5D%20%3C%20s%5Bi%5D%5Bj%5D
[s_i _ 1_j_ _ s_i_j]: https://private.codecogs.com/gif.latex?s%5Bi%20&plus;%201%5D%5Bj%5D%20%3E%20s%5Bi%5D%5Bj%5D
[s_i_j - 1_ _ s_i_j_ _ s_i _ 1_j]: https://private.codecogs.com/gif.latex?s%5Bi%5D%5Bj%20-%201%5D%20%3C%20s%5Bi%5D%5Bj%5D%20%3C%20s%5Bi%20&plus;%201%5D%5Bj%5D