专栏文章

EGOI 2024 P2 - Bouquet

zzhanglh
P10845题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@miptcxny
此快照首次捕获于
2025/12/03 17:37
3 个月前
此快照最后确认于
2025/12/03 17:37
3 个月前
查看原文
考虑 dp。
定义 fif_i 表示考虑前 ii 朵花，第 ii 朵必选，最多可以采几朵花。
fi=max⁡{fj}+1f_i = \max\{f_j\} + 1，其中 j≤i−li−1,j+rj+1≤ij \le i - l_i - 1, j + r_j + 1 \le i。
求 max⁡{fj}\max\{f_j\} 可以用树状数组维护最值。对于 j≤i−li−1j \le i - l_i - 1 的限制，查询前缀 [1,i−li−1][1, i - l_i - 1]。
对于限制 j+rj+1≤ij + r_j + 1 \le i，发现 ii 只对 i+rii + r_i 之后的位置有贡献，因此在第 min⁡(n,i+ri)\min(n, i + r_i) 个位置处理之后再将 fif_i 的值更新到树状数组上。
CPP
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 200010;

int n, l[N], r[N], tr[N], f[N], ans;
vector<int> upd[N];

int lowbit(int i) { return i & -i; }

void update(int x, int k) {
	for (int i = x; i <= n; i += lowbit(i)) tr[i] = max(tr[i], k);
}

int query(int x) {
	int res = 0;
	for (int i = x; i > 0; i -= lowbit(i)) res = max(res, tr[i]);
	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];
	
	for (int i = 1; i <= n; i++) {
		if (i - 1 <= l[i]) f[i] = 1;
		else f[i] = query(i - l[i] - 1) + 1;
		ans = max(ans, f[i]);
		upd[min(n, i + r[i])].push_back(i);
		for (int j : upd[i]) update(j, f[j]);
	}
	
	cout << ans << "\n";
	
	return 0;
}

评论

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

正在加载评论...