CF1889C题解

hyman00 · 2023-10-29 22:14:41 · 题解

CF1889C 题解

题意

有 m 个线段，值域 [1,n]，可以删除至多 k 个，最大化没有被任意一个剩余线段覆盖的位置的个数。

做法

考虑 dp，把所有线段按照左端点从小到大排序，令 dp_{i,x,y} 表示对于前 i 个线段，其中有 x 个删除了，没有删除的右端点最大是 y 时，没有删除的线段最少覆盖了多少个位置。

注意 x 是 [0,k] 中的数，y 虽然范围较大，但是只有前 i 个线段中最大的 k+1 个右端点是有用的（显然这些不可能全删完），状态数 O(nk^2)，需要用 unordered_map 记录。

转移可以枚举当前线段是否删除，是 O(1) 的。

实现细节

dp 数组只开一个 unordered_map，可以把三维压一起，这样不用担心开 2\times 10^6 个会炸，状态可以用 i\times 2^{22}+x\times 2^{18}+y 记录。

转移完一个状态后就可以把它从哈希表里删除，这样同一时刻的哈希表里的元素个数仅有 O(k^2)，常数不会太大。

注意不要 n,m 写反。

总复杂度时间 O(mk^2)，空间 O(m+k^2)。

代码

unordered_map<int,int>dp;
int n,m,k;
pii p[200005];
//i*(k+1)*(n+1)+j*(n+1)+k 
const int C=100000000;
inline void go(int x,int y,int z,int t){
    int w=(x<<22)|(y<<18)|z;
    Mi(dp[w],t-C);
}
void run(){
    cin>>n>>m>>k;
    rep(i,m){
        cin>>p[i].F>>p[i].S;
    }
    if(k>=m){
        cout<<n<<"\n";
        re;
    }
    sort(p,p+m);
    dp.clear();
    set<int>st;
    st.insert(0);
    int ans=n+1;
    go(0,0,0,0);
    rep(i,m){
        for(int l:st)rep(j,min(k,i)+1)if(dp.count((i<<22)|(j<<18)|l)){
            int t=dp[(i<<22)|(j<<18)|l]+C;
            dp.erase((i<<22)|(j<<18)|l);
//          cout<<i<<" "<<j<<" "<<l<<": "<<t<<"\n";
            go(i+1,j,max(l,p[i].S),t+max(p[i].S,l)-max(p[i].F-1,l));
            if(j<k)go(i+1,j+1,l,t);
        }
        st.insert(p[i].S);
        while(sz(st)>k+1)st.erase(st.begin());
    }
    for(int l:st)rep(j,k+1){
//      cout<<m<<" "<<j<<" "<<l<<": "<<dp[(m<<22)|(j<<18)|l]+C<<"\n";
        Mi(ans,dp[(m<<22)|(j<<18)|l]+C);
    }
    cout<<n-ans<<"\n";
}