CF1889C2 Doremy's Drying Plan (Hard Version) 题解
题目链接：Doremy's Drying Plan (Hard Version)
题意：
多组数据。有 \(n\) 个点和 \(m\) 条线段，你可以选择 \(k\) 条线段删除，
要求最大化未被线段覆盖的点的数量，输出最大值。
数据范围：
\(1 \le T \le 10^4,~1 \le \sum n,\sum m \le 2\times 10^5,~2 \le k \le \min(10, m),~1\le l_i \le r_i \le n\) 。
设 \(f(i,x,y)\) 为前 \(i\) 条线段，删除了 \(x\) 条，没有删除的线段的右端点是 \(y\) 时，覆盖位置的最小值。
把线段按左端点升序排序，这样转移考虑枚举当前线段是否被删除即可。
虽然 \(y\) 的值域非常大，但因为只有 \(k+1\) 个极大的右端点是有用的。
于是总状态数为 \(\mathcal{O}(mk^2)\) ，实现的时候可以用 \(i\times 2^{22} + x\times 2^{18} + y\) 的方式压到 unordered_map 里。
注意 operator[]
在访问不存在元素时，会自动创建一个元素，因此不要用 !mp[x]
的方式判断元素是否存在。
时间复杂度 \(\mathcal{O}(mk^2)\)
代码：
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e5 + 15))
#define Fi first
#define Se second
pii a[N]; const int B = 1e9;
unordered_map<int,int> dp; set<int> st;
#define id(x, y, z) (((x) << 22) | ((y) << 18) | (z))
void upd(int x, int y, int z, int t) { down(dp[id(x, y, z)], t - B); }
void solve()
{
int n, m, k; cin >> n >> m >> k;
rep(i, 0, m - 1) cin >> a[i].Fi >> a[i].Se;
if(k >= m) { cout << n << '\n'; return; }
sort(a, a + m); dp.clear(); st.clear(); st.insert(0); upd(0, 0, 0, 0);
rep(i, 0, m - 1)
{
for(int l : st) rep(j, 0, min(k, i))
{
if(!dp.count(id(i, j, l))) continue;
const int t = dp[id(i, j, l)] + B; dp.erase(id(i, j, l));
upd(i + 1, j, max(l, a[i].Se), t + max(a[i].Se, l) - max(a[i].Fi - 1, l));
if(j < k) upd(i + 1, j + 1, l, t);
}
st.insert(a[i].Se); while(st.size() > k + 1) st.erase(st.begin());
}
int res = n + 1;
for(int l : st) rep(j, 0, k) down(res, dp[id(m, j, l)] + B);
cout << n - res << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int qwq; cin >> qwq; while(qwq--) solve();
return 0;
}双倍经验：CF1889C1 Doremy's
Drying Plan (Easy Version) （绿的也算双倍？）
参考文献：
