CF1768F

只能说这题太妙了，场上 tourist 都没过。

题目描述

• 给定一个长度为 $n$ 的序列 $a_1,a_2\dots,a_n$。
• 对于 $1\le i\le j\le n$，你可以花费 $(i-j)^2\cdot\operatorname{min}(a_i,a_{i+1}\dots a_j)$ 的代价从 $i$ 跳到 $j$。
• 你现在要对于所有的 $1\le k\le n$，输出从 $1$ 到 $k$ 的最段路。
• $1\le a_i\le n\le4\times10^5$。

解题思路

首先考虑 $O(n^2)$ 的 DP，$f_i$ 表示从 $1$ 到 $i$ 的最短路径，转移很简单。

现在要考虑把这个 DP 优化到可以接受的时间复杂度内，考虑有以下性质。

性质1

对于 $1\le i\le j\le n$，如果直接从 $i$ 跳到 $j$，那么一定不会比经过区间最小值 $a_k$ 跳两次更优。

证明很简单，如果直接从 $i$ 跳到 $j$，那么代价就是 $a_k\cdot(i-j)^2$。

然而经过 $k$ 的代价是 $a_k\cdot(k-i)^2+a_k\cdot(j-k)^2=a_k\cdot((k-i)^2+(j-k)^2)$。

显然因为对于 $a,b\ge0$，有 $(a+b)^2\ge a^2+b^2$，所以经过区间最小值更优。

由此可知，每一步的区间最小值一定在两端。

性质2

对于一个最小值 $a_i$，一定满足他前面和后面的步长一定不会超过 $n/a_i$。

证明：

对于一个步长 $d$，如果每次只跳 $1$ 的距离，那么每次的花费都不会超过 $n$，总花费不会超过 $n\cdot d$。

然而一步跳到的花费是 $a_i\cdot d^2$。

要满足一步跳到更优，就有 $a_i\cdot d^2\le n\cdot d$，既 $d\le\frac{n}{a_i}$。

时间复杂度

有了以上性质我们就只要对于每个 $i$，考虑以 $a_i$ 为最小值转移既可，可以证明这样的时间复杂度是 $O(n\sqrt n)$ 的。

对于 $a_i\ge\sqrt n$，步长上限 $d=\frac n {a_i}\le\sqrt n$，所以时间复杂度不会超过 $O(n\sqrt n)$。

而对于 $a_i<\sqrt n$，考虑将将同的 $a_i$ 放在一起考虑。

那么对于一个相同的 $a_i$，以他们为最小值的区间长度之和是 $O(n)$。

然而最多有 $\sqrt n$ 种数，所以时间复杂度也不会超过 $O(n\sqrt n)$。

示例代码

代码非常好写。

#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
void debug(...) {}
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define per(i, n) for (int i = (n) - 1; ~i; --i)
#define all(v) (v).begin(), (v).end()
using ll = long long;
using vi = vector<int>;
 
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);
#endif
  constexpr ll inf = 1e18;
  int n;
  cin >> n;
  vi a(n);
  vector<ll> f(n, inf);
  rep(i ,n) cin >> a[i];
  f[0] = 0;
  rep(i, n) {
    int d = n / a[i];
    for (int j = i - 1; j >= 0 && i - j <= d; --j) {
      f[i] = min(f[i], f[j] + 1ll * (i - j) * (i - j) * a[i]);
      if (a[j] <= a[i]) break;
    }
    for (int j = i + 1; j < n && j - i <= d; ++j) {
      f[j] = min(f[j], f[i] + 1ll * (i - j) * (i - j) * a[i]);
      if (a[j] <= a[i]) break;
    }
  }
  rep(i, n) cout << f[i] << ' ';
  cout << '\n';
}