|
题目
题意：给定一个
n
?
1
0
9
n*10^9
n?109的点阵，现在给出m个线段，线段
i
,
l
,
r
i,l,r
i,l,r表示第
i
i
i行区间
[
l
,
r
]
[l,r]
[l,r]取1。现在最少需要删去多少行，才能使得剩下的行中，任何相邻的两行，都至少有一个共同的列，取值都为1。
官方题解
思路：思考最多能保留多少行。
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]表示从第1行到第i行，对于列j来说，能保留的最多行数。则有
d
p
[
i
]
[
j
]
=
1
+
m
a
x
(
d
p
[
i
?
1
]
[
k
]
)
,
k
∈
C
i
,
i
f
g
r
i
d
[
i
]
[
j
]
=
1
dp[i][j] = 1 + max(dp[i-1][k]), k \in C_i, if grid[i][j]=1
dp[i][j]=1+max(dp[i?1][k]),k∈Ci?,ifgrid[i][j]=1
d
p
[
i
]
[
j
]
=
d
p
[
i
?
1
]
[
j
]
,
i
f
g
r
i
d
[
i
]
[
j
]
≠
1
dp[i][j] = dp[i-1][j], if grid[i][j]\neq1
dp[i][j]=dp[i?1][j],ifgrid[i][j]?=1
维护区间的最大值，可以用线段树。由于列范围比较大，需要进行下标压缩。
由于答案要求输出具体删除的行，我们可以用pre数组保存dp状态。详见参考代码。
细节比较多，考察的点也多。太懒了没打代码（其实是太菜了）
代码
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define ONLINE_JUDGE
#define endl "\n"
#define ll long long
#define sz(s) (int)(s.size())
#define INF 0x3f3f3f3f3f3f3f3fLL
#define all(v) v.begin(),v.end()
#define watch(x) cout<<(#x)<<" = "<<x<<endl
const int dr[]{ -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[]{ 0, 1, 1, 1, 0, -1, -1, -1 };
#if __cplusplus >= 201402L
template<typename T>
vector<T> create(size_t n) {
return vector<T>(n);
}
template<typename T, typename ... Args>
auto create(size_t n, Args ... args) {
return vector<decltype(create<T>(args...))>(n, create<T>(args...));
}
#endif
void run() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#else
#endif
}
const pair<int, int> NIL = { 0,-1 };
struct segment_tree {
#define LEFT (idx<<1)
#define RIGHT (idx<<1|1)
#define MID (start+end>>1)
int n;
vector<pair<int, int>> tree, lazy;
segment_tree(int n) :n(n) {
tree = lazy = vector<pair<int, int>>(n << 2, NIL);
}
void push_down(int idx, int start, int end) {
if (lazy[idx] == NIL)
return;
tree[idx] = max(tree[idx], lazy[idx]);
if (start != end) {
lazy[LEFT] = max(lazy[LEFT], lazy[idx]);
lazy[RIGHT] = max(lazy[RIGHT], lazy[idx]);
}
lazy[idx] = NIL;
}
void update(int idx, int start, int end, int l, int r, pair<int, int> p) {
push_down(idx, start, end);
if (r < start || end < l)
return;
if (l <= start && end <= r) {
lazy[idx] = max(lazy[idx], p);
push_down(idx, start, end);
return;
}
update(LEFT, start, MID, l, r, p);
update(RIGHT, MID + 1, end, l, r, p);
tree[idx] = max(tree[LEFT], tree[RIGHT]);
}
pair<int, int> query(int idx, int start, int end, int l, int r) {
push_down(idx, start, end);
if (r < start || end < l)
return NIL;
if (l <= start && end <= r)
return tree[idx];
return max(query(LEFT, start, MID, l, r),
query(RIGHT, MID + 1, end, l, r));
}
void update(int l, int r,pair<int,int> p) {
update(1, 1, n, l, r, p);
}
pair<int, int> query(int l, int r) {
return query(1, 1, n, l, r);
}
};
int main() {
run();
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> v(n);
vector<int> id;
while (m--) {
int i, l, r;
cin >> i >> l >> r;
id.push_back(l);
id.push_back(r);
v[i - 1].push_back({ l,r });
}
sort(all(id));
id.erase(unique(all(id)), id.end());
for (int i = 0; i < n; i++)
for (auto& it : v[i]) {
it.first = upper_bound(all(id), it.first) - id.begin();
it.second = upper_bound(all(id), it.second) - id.begin();
}
segment_tree seg(id.size());
vector<int> prv(n, -1);
for (int i = 0; i < n; i++) {
pair<int, int> mx = NIL;
for (auto& it : v[i])
mx = max(mx, seg.query(it.first, it.second));
prv[i] = mx.second;
mx.first++;
mx.second = i;
for (auto& it : v[i])
seg.update(it.first, it.second, mx);
}
pair<int, int> p = seg.query(1, id.size());
vector<bool> vis(n);
int cur = p.second;
while (cur != -1) {
vis[cur] = true;
cur = prv[cur];
}
cout << n - p.first << endl;
for (int i = 0; i < n; i++)
if (!vis[i])
cout << i + 1 << ' ';
}
|