题解 P1295 【[TJOI2011]书架】

· · 题解

※题目分析

给出一个长度为 n 的序列 h，请将 h 分成若干段，满足每段数字之和都不超过 m，最小化每段的最大值之和。

众所周知，不会做的题目就 DP。其实 DP 方程挺好想的，设 f_i 为到第 i 个数，分为若干段所需要的最小代价；设 sum_{i} 为h 的前缀和。根据题意可以得到转移：

f_i=\min\limits_{sum_i-sum_j\leq m}\left(f_j+\max\limits_{k=j+1}^{i}h_k\right)

这个式子有很多种处理方法，最简单的直接 CDQ 就可以了，线段树题解区的大佬也讲过了，我翻提交记录好像看见了有用堆写的。如果用堆的话，是没有考虑好本题的单调性。

本文要提的是题解区的那个 O(n) 做法。由于这位大佬的题解有一点久远，意思模糊不清，然后还有证明没给出，因此本文重提。

这种做法大概可以理解为用单调性对堆优化吧……

※性质分析

引理一：\max\limits_{k=j+1}^{i}h_k 中，随着 k 的增大，其值单调不增。

引理二：f 单调不降。

参考 CSP-S 2020 T4，我们可以把转移分成两段。

1、对于一个合法的 j，h_{j+1}\leq \left(\max\limits_{k=j+2}^{i}h_k\right)，则 \left(\max\limits_{k=j+1}^{i}h_k\right)=\left(\max\limits_{k=j+2}^{i}h_k\right)；又因为 f 单调不降，f_j\leq f_{j+1}即对于转移 f_j+\left(\max\limits_{k=j+1}^{i}h_k\right)\leq f_{j+1}+\left(\max\limits_{k=j+2}^{i}h_k\right) 。所以此时从 j 转移（j+1 到 i 为一段）比从 j+1 转移更优。

那么此时对于 h 的一个极小值就可能成为转移的最优解。又由于 h 单调不增，所以可以对 h 维护一个单调递减的队列，队尾即转移的可能最优点。

2、对于一个合法的 j，h_{j+1}>\left(\max\limits_{k=j+2}^{i}h_k\right)，可以包含在第一种情况，即我们假设单调队列 q，设左右端点 l,r，则最优的转移会在 q_{l,l+1,\dots,r} 之中；也即 h_{q_l}>h_{q_{l+1}}>\dots>h_{r} 当中转移 f_i（不取等是因为取等的情况一定靠前的更优）。

具体的证明大概是这样的：第一种情况维护的是函数的极小值，其中突出的部分会被包含在两个相邻的极小值当中，但这种转移对队列中的 q_l 不适用！

因为这种情况即从 q_l 转移到 i，那么 q_l 之前的位置应当为第一个位置 st 使得 h_i-h_{st}>m，f_i 就更新为 f_{st}+h_{ql}，否则就越界了。

但维护单调队列的时候就可能产生一些意外使得一些值没被更新到。所以可以维护单调栈防止漏掉情况。具体是这样的，对于第二种情况，有可能直接 h_{j+1} 自己作为一段新的段，并包含之后的数，也就会存在一段连续相等的 f；或者把之前并作一段，这并不会影响转移。

我们发现，当队列元素越多，重构单调栈的次数也就越多，但总的重构次数也越少（仅在对队列弹出过期元素可能重构）。可以考虑把随机数据拆成几段单调下降的序列，最长的最多是最长下降子序列，假设长度为 p。则最多重构 n/p 次，每次最多重构 p 个数，则复杂度最多 O(n/p·p)=O(n)。取到最大时，当最长子序列尽量长，也即 h 严格单调下降。当然并不是严格单调下降就可以取到最大值，还要考虑 h 和 m 之间的关系。

（纯属口胡）

那么考虑 h_i，可以 st+1\sim i 并成一段，f_i=f_{st}+h_{q_l}；若单调栈中有值，则可以在其他的 j>st 并成一段 h\sim i，取最小即可。

可能有人有疑问这里的第一种情况去哪了？其实在一开始维护第一种情况就直接扔到单调栈里就可以了，反正最后是维护最小的。（根据上文提到的单调性，显然是正确的）

（如果后面想到更好的对单调栈的解释我会回来补充的，不过 noip 之后可能就 AFO 了）

综上我们得到了一个 O(n) 的算法。

※代码

我知道你们只看这个 

/*
BY xiejinhao
2020-11-20 9:19 from XWSF
*/

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int h[N], q[N], stk[2][N];
int top[2], l = 1, mid, r;
long long f[N], tmpf[N];

// stk[0/1]  左/右 栈，指针对应 top[0/1]
// q 队列  h 原数组  tmpf 对应队列中的 f 值 

void push(int x, int i) {
    if(!top[i]) stk[i][++top[i]] = x;
    else if(tmpf[stk[i][top[i]]] > tmpf[x])
        stk[i][++top[i]] = x;
}

void rebuild() {
    mid = (l + r) >> 1, top[0] = top[1] = 0;
    for(int i = mid; i >= l; i--) push(i, 0);
    for(int i = mid + 1; i <= r; i++) push(i, 1);
}

int main() {
    int n, m, st = 1, sum = 0;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", h + i), sum += h[i];
        while(sum > m) sum -= h[st++];
        while(l <= r and h[q[r]] <= h[i]) {
            if(top[0] and stk[0][top[0]] == r) --top[0];
            if(top[1] and stk[1][top[1]] == r) --top[1];
            if(--r <= mid) rebuild();
        } // 维护单调队列 
        if(l > r) tmpf[r + 1] = f[st - 1] + h[i];
        else tmpf[r + 1] = f[q[r]] + h[i];
        q[++r] = i, push(r, 1); 

        // 队头的情况要特判 
        if(stk[0][top[0]] == l) --top[0];
        if(stk[1][top[1]] == l) --top[1];
        while(l <= r and q[l] < st) { 
            if(++l > mid) rebuild();
            // 同样特判队头 
            if(top[0] and stk[0][top[0]] == l) --top[0];
            if(top[1] and stk[1][top[1]] == l) --top[1];
        } // 弹出过期元素 

        f[i] = f[st - 1] + h[q[l]]; // 和开头并为一段
        // ---   与开头之后的某个数开始并为一段   --- 
        if(top[0]) f[i] = min(f[i], tmpf[stk[0][top[0]]]);
        if(top[1]) f[i] = min(f[i], tmpf[stk[1][top[1]]]);
    }
    printf("%lld\n", f[n]);
    return 0;
}

※写在后面

1、本文同步发布在我的博客园：点我

2、翻了下提交记录，各位以后抄题解稍微改一下行嘛

3、能点个赞吗（光速逃