自动搬运

查看原文

来自洛谷，原作者为

	Spectator 我趁有半天空档 ／ 为你跑一趟 ／ 城市里永远有宝藏

搬运于2025-08-24 22:45:20，当前版本为作者最后更新于2025-03-21 10:16:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

可能更好的食用体验 $|$ 题目传送门 $|$ 我的其他题解

---

${\color{#00CD00}\text{思路}}$

考虑 $\tt{DP}$。定义 $s_i=\sum\limits_{j=1}^i a_i$，$f_i$ 表示满足前 $i$ 个城市的需求所需的最小花费。根据这个定义，可以得到以下的状态转移方程：

$$f_i = \min_{j=1}^i \left\{f_{j-1} + i - j\right\},s_i - s_{j-1} \ge 0 $$

它的含义是：枚举一个分界点 $j$，如果 $i\sim j$ 这一段城市可以“自给自足”（$s_i - s_{j-1} \ge 0$），就使用 $i-j$ 条电线将 $i\sim j$ 这一段城市连接起来，再加上前 $j-1$ 个城市的花费，求最小的花费。

写成代码是这样的：

memset(f, 0x3f, sizeof(f)), f[0] = 0;
for(int i=1; i<=n; i++){
    for(int j=1; j<=i; j++){
        if(s[i] - s[j-1] >= 0) f[i] = min(f[i], f[j-1] + i - j);
    }
}

朴素的 $\tt{DP}$ 是 $O(n^2)$ 的，会超时。考虑优化转移。观察这个转移方程，发现结果只与 $f_j - j$ 有关。于是可以转化为：对于所有小于等于 $s_i$ 的 $s_j$，求 $f_j - j$ 的最小值。这是可以用树状数组之类的数据结构维护的。于是我们就将转移优化为了 $O(n\log n)$，可以通过本题。

具体地，先将所有的 $s_i$ 离散化，对于每个 $i$，查询 $s_i$ 以内的 $f_j - j$ 的最小值，假设为 $t$，$f_i$ 即为 $t + i - 1$。然后在树状数组中将 $s_i$ 这一位更新为 $f_i - i$ 即可。

---

${\color{#00CD00}\text{代码}}$

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
long long n, s[N], rk[N];
int a[N], f[N];
struct BIT{
	int c[N], lowbit(int x){return x & -x;}; BIT(){memset(c, 0x3f, sizeof(c));}
	void update(int x, int k){while(x < N) c[x] = min(c[x], k), x += lowbit(x);}
	int query(int x){int s = N; while(x) s = min(s, c[x]), x -= lowbit(x); return s;}
} t;
signed main(){
	cin.tie(nullptr) -> sync_with_stdio(false);
	cin >> n; 
	for(int i=1; i<=n; i++) cin >> a[i], rk[i] = s[i] = s[i-1] + a[i];
	sort(rk, rk + 1 + n); int k = unique(rk, rk + 1 + n) - rk;
	for(int i=0; i<=n; i++) s[i] = lower_bound(rk, rk + 1 + k, s[i]) - rk + 1;
	t.update(s[0], 0);
	for(int i=1; i<=n; i++){
		f[i] = t.query(s[i]) + i - 1;
		t.update(s[i], f[i] - i);
	}
	cout << (f[n] > n ? -1 : f[n]);
	return 0;
}