编程四连测之第一测[telephonewire]

忘是亡心i 2022-04-10 06:50 115阅读 0赞

**目录**

题目

解题思路

枚举方向

变量充当单调栈

参考代码

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

# 题目 #

**题目描述**

最近，约翰的奶牛们越来越不满足于牛棚里一塌糊涂的电话服务，于是，她们要求约翰把那些老旧的电话线换成性能更好的新电话线。新的电话线架设在己有的n根电话线杆上，第i根电话线的高度为hi, ( 1 <= hi<= 100)。电话线总是从一根电话线杆的顶端被弓\}到相邻的那根的顶端，如果这两根电话线杆的高度hi和hj不同，那么约翰就必须支付c \* |hi - hj|的费用，当然，你不能移动电话线杆，只能按照原有  
的顺序在相邻杆间架设电话线。

加高某些电话线杆能减少架设电话线的总费用，尽管这项工作也需要支付一定的费用。更准确的说，如果他把一根电话线杆加高x米的话，他需要付出x^2费用。

请你帮约翰计算一下，如果合理的进行这两项工作，他最少要在这个电话线改造工程中花多少钱。

**输入**

第一行输入两个数n (n <= 100000)和c (c <= 100), 含义如上。接下来n行，每行一个整数hi (hi < 100)。

**输出**

输出约翰完成电话线改造工程需要花费的最小费用，保证答案不超过max long int。

**样例输入**

5 2
    2
    3
    5
    1
    4

**样例输出**

## 解题思路 ##

### DP ###

这个题一看就应该是dp吧，但是是几维呢？我觉得不太可能会有人认为这是三维吧（就这数据的大小怎么都会MLE）。

令dp\[i\]\[j\] 为第i根电线杆高度为j时的最小费用，则可以得到 ![dp\[i\]\[j\] = min \\left \\\{ dp\[i - 1\]\[k\] + \\left | j - k \\right | \* c + (j - h\[i\])^\{2\} \\right \\\}][dp_i_j_ _ min _left _ dp_i - 1_k_ _ _left _ j - k _right _ _ c _ _j - h_i_2_ _right]。

其中的k是枚举前一个电线杆的高度。

看起来很复杂？没事，我们来逐一分解。

可以看到，![\\left ( j - h\[i\] \\right )^\{2\}][left _ j - h_i_ _right _2] 是跟当前状态有关，意思也就是说它不参与k的运算，可以独立在外面。这下就变成了:![dp\[i\]\[j\] = min \\left \\\{ dp\[i - 1\]\[k\] + \\left | j - k \\right | \* c \\right \\\} + (j - h\[i\])^\{2\}][dp_i_j_ _ min _left _ dp_i - 1_k_ _ _left _ j - k _right _ _ c _right _ _ _j - h_i_2]。

继续来分，我们现在来把绝对值去掉，就会有两种情况：①j >= k，就会变成![dp\[i\]\[j\] = min \\left \\\{ dp\[i - 1\]\[k\] - k \* c + j \* c \\right \\\} + (j - h\[i\])^\{2\}][dp_i_j_ _ min _left _ dp_i - 1_k_ - k _ c _ j _ c _right _ _ _j - h_i_2]，再把j \* c拿出来，就是![min\\left \\\{ dp\[i - 1\]\[k\] - k \* c \\right \\\} + (j - h\[i\])^\{2\} + j \* c][min_left _ dp_i - 1_k_ - k _ c _right _ _ _j - h_i_2_ _ j _ c]；

②j <= k,就会是![dp\[i\]\[j\] = min \\left \\\{ dp\[i - 1\]\[k\] + k \* c - j \* c \\right \\\} + (j - h\[i\])^\{2\}][dp_i_j_ _ min _left _ dp_i - 1_k_ _ k _ c - j _ c _right _ _ _j - h_i_2]，拿出来，![min\\left \\\{ dp\[i - 1\]\[k\] + k \* c \\right \\\} + (j - h\[i\])^\{2\} - j \* c][min_left _ dp_i - 1_k_ _ k _ c _right _ _ _j - h_i_2_ - j _ c]。

这下子，所需要参与运算的，也就是说要借助以前的状态的就只剩下k了。

### 枚举方向 ###

这里有两种可能性，一种j >= k，就相当于是在j以前计算，那么如果说是从小到大计算的话，那么就可以借助他的上一个来求解，也就是说dp\[i - 1\]\[k\]可以借助dp\[i - 1\]\[k - 1\]来得到。也就相当于，如果你要求dp\[i - 1\]\[k\]的话就需要k次循环来求了，但是dp\[i - 1\]\[k - 1\]是已经求了前面k - 1次，只需要借助它，就只需要O(1)的复杂度。

同理，j <= k的话就应该是从大到小来计算了。

### 变量充当单调栈 ###

可以从上面看到，如果需要单调栈的话，那么只需要栈顶的元素就够了，可是此时栈顶的元素是什么呢？很显然就是dp\[i - 1\]\[k - 1\],可是在用了栈顶之后，就又需要把它弹出去，然后把dp\[i\]\[k\]装进去。

形象点说，也就是说每个栈顶只会被用到一次，用完之后就又被踢出去了。

那这样的话，还不如就用一个变量来充当栈顶来储存上一轮中的最小值算了。

## 参考代码 ##

/*
    这道题可以用dp求解。令dp[i][j] 为第i颗电线杆的高度为j时i前（包含i）的最小值。
    可以得到转移为 dp[i][j] = min(dp[i - 1][k] + |j - k| * c)
    k是枚举i - 1颗的高度，但这里有一个问题，到底是j大还是k大，所以我们需要分两种情况：
    1、j >= k，dp[i][j] = min(dp[i - 1][k] - k * c + j * c)，在j ~ 1中间枚举最小值。
    本来应该是用单调队列枚举最小值，但可以看出，此时最小值只跟i - 1的情况有关，所以可以用变量代替。
    2、j <= k，dp[i][j] = min(dp[i - 1][k] + k * c - j * c),在j ~ 最高高度枚举。
    这里之所以是枚举到最高高度，是因为没有必要在超过最高高度了。
    同时也用一个变量枚举这之间的最小值
    */
    #include <cstdio>
    #include <cstring>
    using namespace std;
    #define MAXN 100000
    #define INF 0x3f3f3f3f
    #define max(a, b) a > b ? a : b
    #define min(a, b) a < b ? a : b
     
    int n, c, h[MAXN + 5], maxh, ans = INF;
    int dp[MAXN + 5][105];
     
    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 < 0){
            putchar ('-');
            x = (~x) + 1;
        }
        if (x / 10)
            print (x / 10);
        putchar (x % 10 + 48);
    }
     
    int main (){
        read (n); read (c);
        for (int i = 1; i <= n; i++){
            read (h[i]);
            maxh = max (maxh, h[i]);
        }
        memset (dp, INF, sizeof (dp));
        for (int i = h[1]; i <= maxh; i++){//考虑边界,dp[1]的情况很单一
            dp[1][i] = (i - h[1]) * (i - h[1]);
        }
        for (int i = 2; i <= n; i++){
            int min1 = INF, min2 = INF;
            for (int j = 0; j < h[i]; j++){//算出从0到j - 1的最小值，即是上面的1情况
                min1 = min (min1, dp[i - 1][j] - j * c);
            }
            for (int j = h[i]; j <= maxh; j++){
                dp[i][j] = min (dp[i][j], min1 + (j - h[i]) * (j - h[i]) + j * c);
                min1 = min (min1, dp[i][j]);//因为从下到上考虑，所以dp[i][j]也要“放进队列”考虑一下
            }
            for (int j = maxh; j >= h[i]; j--){
                min2 = min (min2, dp[i - 1][j] + j * c);
                dp[i][j] = min (dp[i][j], min2 + (j - h[i]) * (j - h[i]) - j * c);
            }
        }
        for (int i = 1; i <= maxh; i++){
            ans = min (ans, dp[n][i]);
        }
        print (ans);
    }

当然，这里有心的人也许会看到，整个dp数组实际上只跟i和i - 1youg有关，那么完全可以用一个滚动数组来求解。

不过这里就先不粘滚动数组的代码了。[有兴趣的可以看这里][Link 1]

[dp_i_j_ _ min _left _ dp_i - 1_k_ _ _left _ j - k _right _ _ c _ _j - h_i_2_ _right]: /images/20220402/8a74b1d3ef9a4f7885513f885e0eeeff.png
[left _ j - h_i_ _right _2]: https://img-blog.csdnimg.cn/20181219104655532
[dp_i_j_ _ min _left _ dp_i - 1_k_ _ _left _ j - k _right _ _ c _right _ _ _j - h_i_2]: /images/20220402/c0d9492a2ba1416cba33d075b4d6c93e.png
[dp_i_j_ _ min _left _ dp_i - 1_k_ - k _ c _ j _ c _right _ _ _j - h_i_2]: https://img-blog.csdnimg.cn/20181219104655575
[min_left _ dp_i - 1_k_ - k _ c _right _ _ _j - h_i_2_ _ j _ c]: /images/20220402/08178b66c31d487899c783f9b6bb90d3.png
[dp_i_j_ _ min _left _ dp_i - 1_k_ _ k _ c - j _ c _right _ _ _j - h_i_2]: https://img-blog.csdnimg.cn/20181219104655610
[min_left _ dp_i - 1_k_ _ k _ c _right _ _ _j - h_i_2_ - j _ c]: /images/20220402/5eb3b2d6e43b4820ab8b04d76a14a11f.png
[Link 1]: https://blog.csdn.net/qq_41814502/article/details/85017224