题解 CF1668C【Make it Increasing】
Anguei
2022-04-20 16:02:26
## 题意
给定长度为 $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]$ 时。
## 代码
```cpp
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);
}
```