状压DP

CF1313D Happy New Year

化简一下题意

给定 nn 条线段,让你覆盖 mm 个点,保证每个点最多被覆盖 kk 次,求最多有多少个点被奇数条线段覆盖

数据范围 1≤n≤105,1≤m≤109,1≤k≤81\le n\le 10^5,1\le m\le 10^9,1\le k\le 8

很明显,时间复杂度不能与 mm 相关,注意到 kk 很小,所以可以考虑状压DP

将线段的端点离散化后存下来,排序后枚举每个端点

定义 fi,jf_{i,j} 表示枚举到前 ii 个点, jj 表示当前覆盖的线段,第 jj 的二进制表示中 1 的数量为覆盖的线段数量

用 viv_i 表示 ii 中有多少个1,len表示两个相邻端点间的距离,mm 表示覆盖了当前线段后的 jj

分情况考虑当前枚举的端点

1.若为左端点

fi,j=max(fi,j,fi−1,j+(vj mod 2)×len)fi,m=max(fi,m,fi−1,j+(vj mod 2)×(len−1))+(vj+1) mod 2)f_{i,j}=max(f_{i,j},f_{i-1,j}+(v_j~mod~2)\times len)\\f_{i,m}=max(f_{i,m},f_{i-1,j}+(v_j~mod~2)\times(len-1))+(v_j+1)~mod~2)

2.若为右端点

fi,j=max(fi,j,fi−1,j+(vj mod 2)×len)fi,j=max(fi,j,fi−1,m+((v[j]+1) mod 2)×(len−1)+vj mod 2)f_{i,j}=max(f_{i,j},f_{i-1,j}+(v_j~mod~2)\times len)\\f_{i,j}=max(f_{i,j},f_{i-1,m}+((v[j]+1)~mod~2)\times(len-1)+v_j~mod~2)

直接看可能有点抽象,这个方程是什么意思呢?我们先从小到大枚举的每个端点,然后枚举当前可以覆盖的线段,对于左端点,分别考虑选或不选这条线段,因为是离散化过后,所以要乘以两个端点的距离

对于右端点,我们枚举的是删除后的覆盖的线段,所以考虑从没有选过这条线段与选了这条线段后删掉转移

结合代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#define INF (1e8)
using namespace std;
const int N = 1e5 + 5, M = 1 << 8;

struct line
{
    int p, op, d;
    bool operator < (const line a) const
    {
        if (p == a.p)//排序记得先处理右端点,避免超过k
            return op < a.op;
        return p < a.p;
    }
    line(int a = 0, int b = 0, int c = 0) {p = a, op = b, d = c;}
} l[2 * N];
int f[2 * N][M + 5], d[11], v[M + 5], cnt;
int n, m, k, now;

void init()
{
    int maxn = (1 << k) - 1;
    sort(l + 1, l + 1 + cnt);
    for (int i = 1; i <= maxn; i++)
        v[i] = v[i - (i & -i)] + 1;
    for (int i = 0; i <= cnt; i++)
        for (int j = 0; j <= maxn; j++)
            f[i][j] = -INF;
    for (int i = 1; i <= k; i++)
        d[i] = -1;
    f[0][0] = 0;
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
    {
        int L, R;
        scanf("%d%d", &L, &R);
        l[++cnt] = line(L, 1, i), l[++cnt] = line(R + 1, -1, i);
    }
    init();
    for (int i = 1; i <= cnt; i++)
    {
        int p = -1;
        if (l[i].op == 1)
        {
            for (int j = 1; j <= k; j++)
                if (d[j] == -1)
                    {p = j, d[j] = l[i].d; break;}
            if (p == -1) continue;
            for (int j = 0; j <= now; j++)
            {
                if ((j & now) == j)
                {
                    f[i][j] = max(f[i][j], f[i - 1][j] + (v[j] & 1) * (l[i].p - l[i - 1].p));
                    f[i][j | (1 << (p - 1))] = max(f[i][j | (1 << (p - 1))], 
                    f[i - 1][j] + (v[j] & 1) * (l[i].p - l[i - 1].p - 1) + (v[j] + 1 & 1));
                }
            }
            now |= 1 << (p - 1);
        }
        else
        {
            for (int j = 1; j <= k; j++)
                if (d[j] == l[i].d)
                    {p = j, d[j] = -1; break;}
            if (p == -1) continue;
            now ^= 1 << (p - 1);
            for (int j = 0; j <= now; j++)
            {
                if ((j & now) == j)
                {
                    f[i][j] = max(f[i][j], f[i - 1][j] + (v[j] & 1) * (l[i].p - l[i - 1].p));
                    f[i][j] = max(f[i][j], f[i - 1][j | (1 << (p - 1))] + 
                    (v[j] + 1 & 1) * (l[i].p - l[i - 1].p - 1) + (v[j] & 1));
                }
            }
        }
    }        
    printf("%d", f[cnt][0]);
    return 0;
}