题意

给定长度为 $n (1 \leq n \leq 5000)$ 的数组 $a$，此外还有初始值全为零的 $b$ 数组。每次操作可以对 $b_i$ 加上 $a_i$，或者减去 $a_i$。

问最小经过多少次操作，可以使得数组 $b$ 严格单调递增？

思路

结论：最优方案中，最终状态的 $b$ 数组，有且仅有一个 $0$。即：有且仅有一个位置可以不进行操作。

• 首先证明最多存在一个 $0$：假设存在多个 $0$，则无法满足 $b$ 数组严格单调递增的条件。故最多存在一个 $0$。
• 再证明存在一个 $0$：假设现在已经有一种 $b$ 数组当中不含 $0$ 的方案：$b_{k-1} < 0$，$b_k > 0$，$b_{k+1} > b_k$。此时一定可以忽略掉对 $b_k$ 的操作，即减少一些操作次数，将 $b_k$ 置零，这依然满足 $b_{k-1} < b_k < b_{k+1}$ 的条件。

数据范围只有 $5000$，支持 $O(n^2)$ 的做法：枚举每个位置作为零点，从这个位置向两边扩展，分别累加两边总共需要多少次操作即可。左边做减法，右边做加法。

注意：一些情况下，答案会爆 int，如 $a = [1, 1, 1, 1000000000, 1, 1000000000, 1, 1, 1]$ 时。

代码

void solution() {
  int n;
  read(n);
  std::vector<int> a(n + 1), b(n + 1);
  for (int i = 1; i <= n; ++i) read(a[i]);
  ll ans = 1e18;
  for (int i = 1; i <= n; ++i) {
    ll sum = 0, now1 = 0, now2 = 0;
    for (int j = i + 1; j <= n; ++j)
      sum += now1 / a[j] + 1, now1 = a[j] * (now1 / a[j] + 1);
    for (int j = i - 1; j >= 1; --j)
      sum += now2 / a[j] + 1, now2 = a[j] * (now2 / a[j] + 1);
    ans = std::min(ans, sum);
  }
  print(ans);
}