2022 年牛客多校第九场 I 题题解

I The Great Wall II

题意：给定长度为 $nn$ 的序列 $\{a_i\}\backslash \{a\_i\backslash \}$，将其划分为连续的 $kk$ 段，每一段的花费为这一段的最大值，问 $k\in [1,n]k\; \backslash in\; [1,n]$ 的最小花费。$n\le 8\times 10^{3}n\; \backslash leq\; 8\backslash times\; 10^3$。

解法：考虑 $f_{k,i}f\_\{k,i\}$ 表示前 $ii$ 个数字分了 $kk$ 段的最小花费，那么朴素转移为 ${\displaystyle f_{k,i}\leftarrow \underset{k-1\le j\le i-1}{}\{f_{k-1,j}+\underset{j+1\le l\le i}{}{a}_l\}}\backslash displaystyle\; f\_\{k,i\}\; \backslash leftarrow\; \backslash min\_\{k-1\backslash leq\; j\; \backslash leq\; i-1\}\; \backslash \{f\_\{k-1,j\}+\backslash max\_\{j+1\; \backslash leq\; l\; \backslash leq\; i\}a\_l\backslash \}$。考虑分层转移，即固定 $kk$，只对 $ii$ 进行转移，则可以利用单调栈和线段树，维护 ${\displaystyle f_{k-1,j}+\underset{j+1\le l\le i}{}{a}_l}\backslash displaystyle\; f\_\{k-1,j\}+\backslash max\_\{j+1\; \backslash leq\; l\; \backslash leq\; i\}\{a\_l\}$ 实现 $\mathcal{O}(n^2\log n)\backslash mathcal\; O(n^2\; \backslash log\; n)$。但是这样很显然还是过不去。

考虑优化掉线段树的 $\log n\backslash log\; n$。由于单调栈中会有弹栈操作，因而可以在弹栈的时候维护出待弹栈部分的 $f_{k-1,j}f\_\{k-1,j\}$ 的最小值。对于更前面的最小值，可以在维护单调栈的增减栈操作的时候，同步维护出栈的前缀 $ff$ 和 $f+\max f+\backslash max$ 的最小值。这样就可以实现 $\mathcal{O}(n^2)\backslash mathcal\; O(n^2)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 8000, inf = 0x3f3f3f3f;
int a[N + 5], pre[N + 5], f[N + 5][N + 5];
int main()
{
    memset(f, 0x3f, sizeof(f));
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n;i++)
    {
        scanf("%d", &a[i]);
        f[i][1] = pre[i] = max(pre[i - 1], a[i]);
    }
    for (int k = 2; k <= n; ++k)
    {
        vector<int> st, minf, minall;
        st.push_back(inf);
        minf.push_back(0);
        minall.push_back(inf);
        for (int i = 1; i <= n; i++)
        {
            int now = f[i - 1][k - 1];
            while (!st.empty() && st.back() <= a[i])
            {
                now = min(now, minf.back());
                minf.pop_back();
                minall.pop_back();
                st.pop_back();
            }
            f[i][k] = min(now + a[i], minall.back());
            st.push_back(a[i]);
            minf.push_back(now);
            minall.push_back(min(now + a[i], minall.back()));
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%d\n", f[n][i]);
    return 0;
}