这题要是场切可改命了啊!
太可惜了,如此接近正解。
给定 \(n\) 行无限长的 01 串,求最少删除几个满足相邻的上下有连续 \(1\),输出方案。
死就死在这个输出方案上。
看到题先考虑 dp,\(f_i\) 是到 \(i\) 的答案。
得到方程 \(f_i = \min \{f_j + i - j - 1\}\),条件是 \(i\) 和 \(j\) 要能连上,移项得 \(f_i = i + \min\{f_j - j - 1\}\),这个 \(\min\) 用线段树维护就好了,区间修改区间查询。
但是!但是!但是!构造方案不能直接像背包一样用 \(f\) 数组倒推啊!!!
这里的转移并不是没有限制的!得老老实实记录转移来的地方啊!
痛失 D!
警告!
在 dp 输出方案中,请记录转移来的状态,而不是根据最后答案来倒推!
代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#define fi first
#define se second
#define mapa std::make_pair
const int N = 600005, INF = 0x3f3f3f3f;
int n, m, ans = INF, MAX, f[N], flag[N], ai, pre[N];
std::pair<int, int> t[4*N], tag[4*N];
std::vector<int> b;
std::vector<std::pair<int, int> > li[N];
void pushdown(int p) {
t[p+p] = std::min(t[p+p], tag[p]);
tag[p+p] = std::min(tag[p+p], tag[p]);
t[p+p+1] = std::min(t[p+p+1], tag[p]);
tag[p+p+1] = std::min(tag[p+p+1], tag[p]);
tag[p] = mapa(INF, 0);
}
void pushup(int p) { t[p] = std::min(t[p+p], t[p+p+1]); }
std::pair<int, int> Query(int p, int l, int r, int x, int y) {
if (l == x && r == y) return t[p];
pushdown(p);
int mid = l + (r-l) / 2;
if (y <= mid) return Query(p+p, l, mid, x, y);
else if (x > mid) return Query(p+p+1, mid+1, r, x, y);
else return std::min(Query(p+p, l, mid, x, mid), Query(p+p+1, mid+1, r, mid+1, y));
}
void Update(int p, int l, int r, int x, int y, std::pair<int, int> z) {
if (l == x && r == y) {
t[p] = std::min(t[p], z), tag[p] = std::min(tag[p], z);
return;
}
pushdown(p);
int mid = l + (r-l) / 2;
if (y <= mid) Update(p+p, l, mid, x, y, z);
else if (x > mid) Update(p+p+1, mid+1, r, x, y, z);
else Update(p+p, l, mid, x, mid, z), Update(p+p+1, mid+1, r, mid+1, y, z);
pushup(p);
}
void build(int p, int l, int r) {
if (l == r) {
t[p] = mapa(-1, 0), tag[p] = mapa(INF, 0);
return;
}
int mid = l + (r-l) / 2;
build(p+p, l, mid), build(p+p+1, mid+1, r);
pushup(p);
}
int main() {
std::cin >> n >> m;
for (int i = 1, x, l, r; i <= m; i++) {
std::cin >> x >> l >> r;
li[x].push_back(mapa(l, r));
b.push_back(l), b.push_back(r);
}
std::sort(b.begin(), b.end());
MAX = b.size() + 1;
b.erase(std::unique(b.begin(), b.end()), b.end());
for (int i = 1; i <= n; i++)
for (int j = 0; j < (int)li[i].size(); j++)
li[i][j].fi = std::lower_bound(b.begin(), b.end(), li[i][j].fi) - b.begin() + 1,
li[i][j].se = std::lower_bound(b.begin(), b.end(), li[i][j].se) - b.begin() + 1;
build(1, 1, MAX);
for (int i = 1; i <= n; i++) {
int min = INF, pr = 0;
for (int j = 0; j < (int)li[i].size(); j++) {
std::pair<int, int> now = Query(1, 1, MAX, li[i][j].fi, li[i][j].se);
if (now.fi < min) min = now.fi, pr = now.se;
}
int fi = min + i;
f[i] = fi, pre[i] = pr;
if (fi + n-i < ans) ans = fi + n-i, ai = i;
for (int j = 0; j < (int)li[i].size(); j++)
Update(1, 1, MAX, li[i][j].fi, li[i][j].se, mapa(fi - i - 1, i));
}
while (ai) { flag[ai] = 1; ai = pre[ai]; }
std::cout << ans << ‘\n‘;
for (int i = 1; i <= n; i++)
if (!flag[i]) std::cout << i << ‘ ‘;
}
这比赛算是给我提了个醒了!