1 条题解
-
0
考虑 dp。
定义 表示考虑前 朵花,第 朵必选,最多可以采几朵花。
,其中 。
求 可以用树状数组维护最值。对于 的限制,查询前缀 。
对于限制 ,发现 只对 之后的位置有贡献,因此在第 个位置处理之后再将 的值更新到树状数组上。
#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
信息
- ID
- 10942
- 时间
- 3000ms
- 内存
- 1024MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者