Solution. CF1768F Wonderful Jump

Description

给定序列 $a_1,a_2,\dots,a_n$。

每次操作可以从 $i$ 跳到 $j$，费用为 $\min\{a_i,a_{i+1},\dots,a_j\}\times (j-i)^2$。

对于每个 $k,1\le k\le n$，求出从 $1$ 到达 $k$ 的最小费用。

Solution

首先有一个显然的 $O(n^2)$ dp，不多赘述。

假如我们每次进行距离为 $1$ 的跳跃，不难发现从 $i$ 到 $j$ 的费用不会超过 $n\times (j-i)$，于是我们有：
$$
\min\{a_i,a_{i+1},\dots,a_j\}\times(j-i)^2\le n\times(j-i)
$$
也就是：
$$
\min\{a_i,a_{i+1},\dots,a_j\}\times(j-i)\le n
$$
这启发我们进行根号分治。

对于 $\min > \sqrt n$ 的情况，我们只需要考虑 $j$ 之前的 $\sqrt n $ 个位置进行转移。

而 $\min\le\sqrt n$ 时则困难一些。

一个 Observation 是，由于相邻两次跳跃取 $\min$ 的部分有一个数重叠，所以对于一次跳跃，$i$ 到 $j$ 之间不应该存在比 $a_i,a_j$ 更小的数，否则我们完全可以途径这个更小的数多跳一次，很显然这样更优。

于是，我们有 $\min\{a_i,\dots,a_j\}=\min\{a_i,a_j\}$。

如果 $\min\{a_i,a_j\}=a_i$，我们只需要开一个桶记录对于 $k\le\sqrt n$，最后一个满足 $a_p=k$ 的 $p$，每次遍历桶中记录的所有位置进行转移即可。

如果 $\min\{a_i,a_j\}=a_j$，我们知道 $i$ 到 $j$ 之间没有比 $a_j$ 更大的数，我们可以暴力从 $j-1$ 开始向前扫，直到 $a_i\ge a_j$，这样做是均摊 $O(\sqrt n)$ 的，当然我们要证明这件事情。

考虑每个数最多会被扫到多少次。

如果 $a_i$ 在处理 $j,k,j<k$ 时都被扫到，这说明 $a_j<a_k$，同时，$a_j,a_k\le \sqrt n$，所以这样的位置最多只有 $\sqrt n$ 个，$a_i$ 最多被扫到 $\sqrt n$ 次，这样就完成了对均摊根号的证明。

总复杂度为 $O(n\sqrt n)$。

注意在具体实现时，不需要进行分类讨论，也不需要求 $i,j$ 之间所有数的最小值，直接认为最小值为 $\min\{a_i,a_j\}$ 并从所有可能的转移点进行转移即可，我们一定会从最优转移点进行正确的转移，这样就已经保证了正确性。

Code

namespace Main{
    const int N = 400005;
    int n, d, a[N];
    ll f[N], g[N];
    void Main(){
        input(n);
        d = sqrt(n);
        for(int i = 0; i < n; i++) input(a[i]);
        memset(f, 0x3f, sizeof(f));
        memset(g, -1, sizeof(g));
        f[0] = 0;
        if(a[0] <= d) g[a[0]] = 0;
        auto sqr = [](ll x){ return x * x; };
        for(int i = 1; i < n; i++){
            for(int j = i - 1; j >= 0 && j > i - d; j--){
                f[i] = min(f[i], f[j] + min(a[i], a[j]) * sqr(i - j));
            }
            for(int j = 1; j <= d; j++){
                if(g[j] == -1) continue;
                f[i] = min(f[i], f[g[j]] + min(a[i], j) * sqr(i - g[j]));
            }
            if(a[i] <= d){
                for(int j = i - 1; j >= 0 && a[j] > a[i]; j--){
                    f[i] = min(f[i], f[j] + min(a[i], a[j]) * sqr(i - j));
                }
                g[a[i]] = i;
            }
        }
        for(int i = 0; i < n; i++) write(f[i]), putchar(' ');
        return;
    }
} // namespace

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。