AcWing_299 裁剪序列(动态规划、单调队列、区间维护、stl，multiset)

20 Feb 2024 1334字 5分

AcWing

299. 裁剪序列

DP：定义 $f[i]$ ：前 $i$ 个元素的所有划分方式中最大值和的最小值。当 $i=n$ 时， $f[n]$ 即为所求。任取序列 $a[1, i]$ 的最后一段 $j\sim i$ ，假设最大长度为 $k$ ，则有 $j\in[i-k+1, i]$ ， $f[i] = \min_j{{f[j - 1] + a_{max}[j, i]}}$ . 这样，迭代 $i$ , $j$ , $\max_ja[j]$ ，总体的时间复杂度是 $O(n^3)$ . 下面考虑优化：

在从右到左迭代 $j$ 的同时，可以同时取得 $\max_ja[j]$ ，优化到 $O(n^2)$ ；注意到在 $j\in[i-k+1, i]$ 时， $f[j]$ 具有单调性，而 $a_{max}[j, i]$ 具有离散性，所以考虑在区间 $[i - k + 1, i]$ 维护一个单调队列（单调递减） $[k_1, k_2, k_3, \cdots ]$ ， $k_1 + f[k - 1]$ 与 $k_2 + f[k_1]$ ， $k_3 + f[k_2]$ ， $\cdots$ ， $k_N + f[k_{N - 1}]$ 共同构成了 $f[i]$ 所有可能的最小值，使用multiset来维护（因为可能有相同大小的值），其底层基于红黑树实现，使得修改的效率为 $O(logn)$ ；再加上区间维护（双指针） $O(n)$ 的时间复杂度，算法总体的时间复杂度减小到 $O(nlogn)$ .

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, a[N], q[N];  // q存单调队列中的值在a中的下标
multiset<long long> res;
long long m, f[N];
void rmv(long long x){
    auto it = res.find(x);
    res.erase(it);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        if(a[i] > m){
            cout << -1 << endl;
            return 0;
        }
    }
    int hh = 1, tt = 0, k = 1;
    long long sm = 0;
    for(int i = 1; i <= n; i++){
        sm += a[i];
        while(hh <= tt && a[i] >= a[q[tt]]){
            if(hh < tt) rmv(f[q[tt - 1]] + a[q[tt]]);
            tt--;
        }
        q[++tt] = i;
        if(hh < tt) res.insert(f[q[tt - 1]] + a[q[tt]]);
        while(sm > m){
            sm -= a[k];
            k++;
        }
        while(hh <= tt && q[hh] < k){
            if(hh < tt) rmv(f[q[hh]] + a[q[hh + 1]]);
            hh++;
        }
        f[i] = f[k - 1] + a[q[hh]];
        if(!res.empty()) f[i] = min(f[i], *res.begin());
    }
    cout << f[n] << '\n';
    return 0;
}