P9097 [PA 2020] Elektrownie i fabryki 题解

_Spectator_ · 2025-03-21 10:16:52 · 题解

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

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

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

它的含义是：枚举一个分界点 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;
}