专栏文章

题解：P9097 [PA2020] Elektrownie i fabryki

llovely_nst
P9097题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqh4n5t
此快照首次捕获于
2025/12/04 04:43
3 个月前
此快照最后确认于
2025/12/04 04:43
3 个月前
查看原文

P9097 [PA2020] EIF

前置

  1. 分段 DP
  2. 树状数组
  3. 二分等其它算法

正文

设 fif_i 为以 ii 为一段区间结束点，前 ii 个点的最小连边数。可以易得以下转移方程：
fi=min⁡{fj+(i−j−1)∣(∑k=j+1iai)≥0}f_i=\min\{f_j+(i-j-1)|(\sum_{k=j+1}^ia_i)\ge 0\}
时间复杂度为 O(n3)O(n^3)，用前缀和可优化为 O(n2)O(n^2)。
接下来要优化，发现转移方程可以写成：
fi=i−1+min⁡{fj−j∣(∑k=j+1iai)≥0}f_i=i-1+\min\{f_j-j|(\sum_{k=j+1}^ia_i)\ge 0\}
只与 fj−jf_j-j 的值有关。若前缀和 sr≥sl−1(l≤r)s_r\ge s_{l-1}(l\le r)，则 (∑k=lrai)≥0(\sum_{k=l}^ra_i)\ge 0。因此用树状数组维护即可，记得离散化。

AC Code

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...