题解：P9097 [PA2020] Elektrownie i fabryki

lovely_nst · 2025-01-18 12:41:50 · 题解

P9097 [PA2020] EIF

前置

1. 分段 DP

2. 树状数组

3. 二分等其它算法

正文

设 f_i 为以 i 为一段区间结束点，前 i 个点的最小连边数。可以易得以下转移方程：

时间复杂度为 O(n^3)，用前缀和可优化为 O(n^2)。

接下来要优化，发现转移方程可以写成：

只与 f_j-j 的值有关。若前缀和 s_r\ge s_{l-1}(l\le r)，则 (\sum_{k=l}^ra_i)\ge 0。因此用树状数组维护即可，记得离散化。

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n , m , x , s[500005] , S[500005] , d[500005] , f[500005];
void upd (int pos , int c) { while (pos <= m) d[pos] = min (d[pos] , c) , pos += (pos & -pos); }
int qry (int pos) { int ans = 1e9; while (pos) ans = min (ans , d[pos]) , pos -= (pos & -pos); return ans; }
signed main ()
{
    ios::sync_with_stdio (0) , cin.tie () , cout.tie ();
    cin >> n;
    for (int i = 1;i <= n;i ++)
        cin >> x , S[i] = s[i] = s[i - 1] + x , d[i] = 1e18;
    d[n + 1] = 1e18;
    sort (S + 1 , S + n + 2);
    m = unique (S + 1 , S + n + 2) - S - 1;
    for (int i = 1;i <= m;i ++)
        if (S[i] == 0)
            upd (i , 0);
    for (int i = 1;i <= n;i ++)
    {
        int fd = lower_bound (S + 1 , S + m + 1 , s[i]) - S;
        f[i] = qry (fd) + i - 1;
        upd (fd , f[i] - i);
    }
    if (f[n] > n)
        f[n] = -1;
    cout << f[n];
    return 0;
}