1 条题解
-
0
[W] Intervals(dp_w)题解
题意简述
构造长度为 的 01 串。给定 个区间 ,若区间内至少有一个
1则得 ( 可为负),求最大总分。思路
转化:总分 = 全部 − 未满足区间的
把所有 加起来,得到"假设全部满足"的总分;再从里面减掉那些"一个
1都没有"的区间带来的 。于是变成最小化损失。0 段的结构
串中的
1把串切成若干"全 0 段"。一个区间若全落在某个 0 段内则未被满足;若它跨越了两个不同的 0 段,中间必有1,则被满足。因此——未满足的区间 = 被某个极大 0 段 完整包含的区间。
于是只需决定"哪些位置作为 0 段的结束",损失可分解为各 0 段的贡献之和。
DP 定义
- = 前缀 且 处为 0 时的最小损失;
- = 前缀 且 处为
1时的最小损失。
转移:
$$H_e = \min(G_{e-1}, H_{e-1}) \quad (\text{位置 } e \text{ 放 } 1,\text{损失不增加}),$$$$G_e = \min_{i \le e} \left( \text{base}(i) + \text{cost}(i, e) \right),$$其中 、(),而
$$\text{cost}(i,e) = \sum_{k:\; i \le l_k,\, r_k \le e} a_k .$$用线段树维护
上式等价于:维护一个数组 ,。
逐个 推进时:
- 激活 :把 从 设为 (此前没有合法区间能覆盖"以 结尾的 0 段",所以 处不可能被任何区间贡献,先激活是安全的);
- 对每个 的区间,所有满足 的 都要加上 → 区间加 ;
- 区间 的 最小值。
最后答案 。
复杂度
时间 ,空间 。
参考代码
#include <cstdio> #include <climits> #include <algorithm> #include <vector> using namespace std; typedef long long ll; vector<ll> mn, lz; int n_; void build(int o, int l, int r) { if (l == r) { mn[o] = LLONG_MAX / 4; return; } int m = (l + r) >> 1; build(o << 1, l, m); build(o << 1 | 1, m + 1, r); mn[o] = min(mn[o << 1], mn[o << 1 | 1]); } void push(int o) { if (!lz[o]) return; for (int c = o << 1; c <= (o << 1 | 1); c++) { mn[c] += lz[o]; lz[c] += lz[o]; } lz[o] = 0; } void upd(int o, int l, int r, int ql, int qr, ll v) { if (qr < l || r < ql) return; if (ql <= l && r <= qr) { mn[o] += v; lz[o] += v; return; } push(o); int m = (l + r) >> 1; upd(o << 1, l, m, ql, qr, v); upd(o << 1 | 1, m + 1, r, ql, qr, v); mn[o] = min(mn[o << 1], mn[o << 1 | 1]); } void activate(int o, int l, int r, int pos, ll val) { if (l == r) { mn[o] = min(mn[o], val); return; } push(o); int m = (l + r) >> 1; if (pos <= m) activate(o << 1, l, m, pos, val); else activate(o << 1 | 1, m + 1, r, pos, val); mn[o] = min(mn[o << 1], mn[o << 1 | 1]); } ll qry(int o, int l, int r, int ql, int qr) { if (qr < l || r < ql) return LLONG_MAX / 4; if (ql <= l && r <= qr) return mn[o]; push(o); int m = (l + r) >> 1; return min(qry(o << 1, l, m, ql, qr), qry(o << 1 | 1, m + 1, r, ql, qr)); } int main() { int n, m; scanf("%d %d", &n, &m); vector<vector<pair<int, ll>>> byR(n + 1); ll total = 0; for (int i = 0; i < m; i++) { int l, r; ll a; scanf("%d %d %lld", &l, &r, &a); byR[r].push_back({l, a}); total += a; } mn.assign(4 * n + 4, 0); lz.assign(4 * n + 4, 0); build(1, 1, n); ll H = 0, Gprev = LLONG_MAX / 4, best = 0; for (int e = 1; e <= n; e++) { activate(1, 1, n, e, (e == 1) ? 0 : H); // base(e) for (auto& pr : byR[e]) upd(1, 1, n, 1, pr.first, pr.second); ll G = qry(1, 1, n, 1, e); H = (e == 1) ? 0 : min(H, Gprev); Gprev = G; best = min(G, H); } printf("%lld\n", total - best); return 0; }易错点
- 必须先激活叶 再加区间:否则"以 结尾的 0 段"可能被更早的区间错误地累加到 ,导致该段永远不可用。
- 激活值应取 ( 取 0),而不是 ——位置 必须是
1才能把 0 段断开。 - 全部 时最优是全
1(答案 );全负时最优是全 0,但因为要"至少满足"……注意全 0 串也会满足"含 1 至少一次"?不,全 0 时所有区间都不满足,答案 。 - 答案可达 ,必须
long long。
数据说明
共 16 组:5 组官方样例; 手工构造; 随机; 全正、全负、混合随机三组,以及"一个大正区间 + 大量小区间"的构造组。
- 1
信息
- ID
- 32
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者