序列长度为 \(m\)，初态为 \(0\)，你可以从 \(n\) 个操作中选择若干个执行，第 \(i\) 个操作对区间 \([l_i,r_i]\) 中每个位置加上 \(1\)，最大化最后是奇数的元素个数。保证如果施加了所有操作，一个元素的最大值不会超过 \(k \leq 8\)
Solution
首先将所有区间离散化成左闭右开区间，考虑状压 dp，为每个区间分配编号，编号的分配范围是 \(0\to k-1\)，保证没有重叠即可，这样即可设状态为 \(f[i][j]\) 表示考虑到了第 \(i\) 个位置，在 \([pos_{i-1},pos_i)\) 这段区间内的有效状态是 \(j\)，在 \([1,pos_i)\) 这段区间内收获的最大值
转移时，如果这个位置是结束也是开始，那么就可以选择保持或者改变；如果这个位置是结束，那么这个位就归零；如果这个位置是开始，那么决策是否打开。为了方便，我们在第 \(i\) 个位置上做区间 \([pos_{i-1},pos_i)\) 的决策，这样如果 \(popcount(j)\) 是奇数，就算上这一段的贡献，否则不算
没想到一个状压 DP 把我卡死了
#include <bits/stdc++.h>
using namespace std;
#define int long long
map <int,int> mp;
const int N = 200005;
const int M = 256;
int n,m,k,pos[N],f[N][M],l[N],r[N],num[N],isl[9][N],isr[9][N],ind;
struct range {
int l,r;
bool operator < (const range &b) {
return l<b.l;
}
} R[N];
void sh(int &x,int y) {
x=max(x,y);
}
signed main() {
ios::sync_with_stdio(false);
cin >> m >> n >> k;
for (int i = 1; i <= m; i++) {
cin >> l[i] >> r[i];
r[i]++;
mp[l[i]]++;
mp[r[i]]++;
}
for (auto i = mp.begin(); i != mp.end(); i++) i->second = ++ind, pos[ind] = i->first;
for (int i = 1; i <= m; i++) {
l[i] = mp[l[i]];
r[i] = mp[r[i]];
R[i] = { l[i],r[i] };
}
sort(R + 1, R + m + 1);
for (int i = 1; i <= m; i++) {
l[i] = R[i].l;
r[i] = R[i].r;
}
for (int i = 1; i <= k; i++) {
int p = 1;
for (int j = 1; j <= m; j++) {
if (num[j] == 0 && p <= l[j]) {
p = r[j];
num[j] = i;
}
}
}
for (int i = 1; i <= m; i++) {
isl[num[i]][l[i]] = 1;
isr[num[i]][r[i]] = 1;
}
memset(f, -0x3f, sizeof f);
f[0][0] = 0;
pos[0] = 1; //!
for (int i = 1; i <= ind; i++) {
for (int s = 0; s < 1 << k; s++)
if (__builtin_popcount(s)&1)
f[i - 1][s] += (pos[i] - pos[i - 1]);
for (int j = 1; j <= k; j++) {
if (isl[j][i] || isr[j][i]) {
memset(f[i],-0x3f,sizeof f[i]);
for (int s = 0; s < 1 << k; s++) {
if (isl[j][i] && isr[j][i]) {
sh(f[i][s], f[i - 1][s]);
sh(f[i][s ^ (1 << (j - 1))], f[i - 1][s]);
}
if (isl[j][i] && !isr[j][i]) {
if(!(s&(1<<(j-1)))) sh(f[i][s], f[i - 1][s]);
sh(f[i][s | (1 << (j - 1))], f[i - 1][s]);
}
if (!isl[j][i] && isr[j][i]) {
sh(f[i][s & ~(1 << (j - 1))], f[i - 1][s]);
}
}
for (int s = 0; s < 1 << k; s++) f[i - 1][s] = f[i][s];
}
}
}
cout << f[ind][0];
}