[扫描线] [状压dp] CF1313D
_Cheems
·
·
个人记录
思路
然后开个数组 $d$ 实时记录覆盖 $i$ 的区间编号，那么可以设 $f_{i,S}$ 表示考虑前 $i$ 且覆盖到 $i$ 的区间状态为 $S$，这里的 $S$ 需与 $d$ 结合使用。
如何转移？可以略为改变下状态，使其表示填到 $a_i-1$ 个格子，并且 $S$ 状态中的区间将接到 $i+1$ 个点，这样就很容易做了。
那么转移分为衔接 $i-1$ 和为 $i+1$ 准备（这里要分起始点和终结点讨论）。
我的思路比较奇妙，具体看代码吧，感觉一看就懂。
实现时需注意：对点排序时还需使 `op` 作为第二关键字，让终结点优先。否则若重复的端点过多，可能会使得 `d` 数组大小爆掉。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define MAX(a, b) (a) = max((a), (b))
const int N = 2e5 + 5, K = 8, KK = 1 << 8;
int n, m, k, l, r;
int f[N][KK], ct[KK], inf, d[K], ans;
struct node{int op, x, id;}a[N];
inline bool cmp(node A, node B) {return A.x == B.x ? A.op < B.op : A.x < B.x;}
signed main(){
cin >> m >> n >> k;
for(int i = 1; i <= m;++i){
scanf("%d%d", &l, &r);
a[i] = {1, l, i}, a[i + m] = {-1, r + 1, i};
}
m <<= 1;
sort(a + 1, a + 1 + m, cmp);
memset(f, -0x3f, sizeof f), ans = inf = f[0][0], f[0][0] = 0;
for(int i = 1; i < KK; ++i) ct[i] = ct[i ^ (i & -i)] ^ 1; //count(i)%2
for(int i = 1; i <= m; ++i){
for(int S = 0; S < KK; ++S) //衔接i-1
if(f[i - 1][S] ^ inf) MAX(f[i][S], f[i - 1][S] + ct[S] * (a[i].x - a[i - 1].x));
int now;
if(a[i].op == 1){
for(int j = 0; j < k; ++j)
if(!d[j]) {now = j, d[j] = a[i].id; break;} //更新d
for(int S = KK - 1; S >= 0; --S) //倒序防止重复
if(f[i][S] ^ inf) MAX(f[i][S | (1 << now)], f[i][S]); //可以新舔now区间留给i+1
}
else{
for(int j = 0; j < k; ++j)
if(d[j] == a[i].id) {now = j, d[j] = 0; break;} //更新d
for(int S = 0; S < KK; ++S) //正序，理由同上
if((S >> now) & 1) MAX(f[i][S ^ (1 << now)], f[i][S]), f[i][S] = inf; //如S包含now区间，则必须去掉now
}
}
for(int S = 0; S < KK; ++S) ans = max(ans, f[m][S]);
cout << ans;
return 0;
}
```