CF1768F

bulijoijiodibuliduo · 2023-01-06 01:56:00 · 题解

只能说这题太妙了，场上 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 的最段路。

解题思路

首先考虑 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';
}