「poj 3017」Cut the Sequence (DP+堆+单调队列)

poj 3017
给定一个数列$a_n$，任意将连续的$a_i$分块，使所有块的和都不超过$M$，最小化各块的最大值的和。

设$dp(i)$为前$i$个的最优值。
$$
dp(i)=\min(dp(j)+\max(a[j,i-1]))
$$

这个是$O(n^2)$的。考虑优化。
这里$\max(a[j,i-1])$不能表示为多项式，所以不能斜率优化了。
那么我们考虑缩小候选集合$j$的大小。

引理：

若$j$可能成为$f(i)$的最优决策，则必有$a_j > \max[j+1,i]$

证明很容易，假设如果$a_k \leq \max[k+1,i]$，那么我们可以在前面找到一个位置$k$，使得$a_k > \max[k+1,i]$，然后因为$f(i)$单调递增，所以$k$比$j$优，证毕。

那么我们可以维护一个单调队列，满足$a_i - a_{q_{l}} \leq m$，且对于$i$单增则$a_i$单减。
那么对于每个$q_k$，他转移到$i$的代价为$dp(q_k)+a(q_{k+1})$，显然$[q_k,i]$的最大值为$a(q_{k+1})$。
那么

$$
dp(i)=\min_{k \in [j,i]} (dp(q_k)+a(q_{k+1}))
$$

发现$dp(q_k)+a(q_{k+1})$与$i$无关，用数据结构维护之。
这里可以用堆来维护，将单调队列和堆构成一一映射关系，堆维护$\min_{k \in [j,i]} (dp(q_k)+a(q_{k+1}))$，然后每次查询即可。这里方便删除可以用multiset

1、方便删除的堆可以用multiset

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    LL n, m, a[100000 + 5], q[100000 + 5], sum[100000 + 5], dp[100000 + 5];

    multiset<LL > s;

    void clean() {
        ms(sum, 0), ms(q, 0), ms(dp, 0);
    }
    int solve() {

        clean();

        scanf("%lld%lld", &n, &m);
        for (LL i = 1; i <= n; ++i) {
            scanf("%lld", &a[i]), sum[i] = sum[i - 1] + a[i];
            if (a[i] > m) return printf("-1\n"), 0;
        }

        LL l = 1, r = 0, p = 0;
        for (LL i = 1; i <= n; ++i) {
            while (sum[i] - sum[p] > m) ++p;
            while (l <= r && q[l] <= p) {
                if (l < r) s.erase(dp[q[l]] + a[q[l + 1]]);
                ++l;
            }
            while (l <= r && a[q[r]] <= a[i]) {
                if (l < r) s.erase(dp[q[r - 1]] + a[q[r]]);
                --r;
            }
            q[++r] = i;
            if (l < r) s.insert(dp[q[r - 1]] + a[i]);
            dp[i] = dp[p] + a[q[l]];
            if (l < r) dp[i] = min(dp[i], *s.begin());
        }

        cout << dp[n];

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}