题解 B 七彩线段

状态压缩DP。

先将所有位置离散化，然后在每一个 $r_i$ 的 vector 中插入 $l_i$ 和 $c_i$ ，当枚举到 $r_i$ 时，可以从 $l_i-1$ 转移而来，令当前状态为 $k$ ，则 $dp[r_i][k]=max(dp[r_i-1][k],max(dp[l_i-1][k],dp[l_i-1][k~xor~(1<<c_i-1)])+pos[r_i]-pos[l_i])$ ，其中 $pos$ 表示离散化后某个位置代表的真实位置。

时间复杂度 $O(2^7n)$

#include<bits/stdc++.h>
#define re //register
using namespace std;
inline int read(){
    re int t=0;re char v=getchar();
    while(v<'0')v=getchar();
    while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
    return t;
}
vector<int>v[200002];
int n,ans,m,a[100002],b[100002],c[100002],l[100002],r[200002],pos[200002],cnt,dp[200002][129];
signed main(){
    n=read();m=read();
    for(re int i=1;i<=n;++i){
        a[i]=read(),b[i]=read(),c[i]=read();
        r[++cnt]=a[i],r[++cnt]=b[i];
    }
    sort(r+1,r+cnt+1);
    for(re int i=1;i<=n;++i)pos[lower_bound(r+1,r+cnt+1,a[i])-r]=a[i],a[i]=lower_bound(r+1,r+cnt+1,a[i])-r;
    for(re int i=1;i<=n;++i)pos[lower_bound(r+1,r+cnt+1,b[i])-r]=b[i],b[i]=lower_bound(r+1,r+cnt+1,b[i])-r;
    for(re int i=1;i<=n;++i)v[b[i]].push_back(a[i]),v[b[i]].push_back(c[i]);
    memset(dp,-127,sizeof(dp));
    dp[0][0]=0;
    for(re int i=1;i<=cnt;++i){dp[i][0]=0;
        for(re int j=0;j<(1<<7);++j)dp[i][j]=dp[i-1][j];
        for(re int j=0;j<v[i].size();j+=2){
            re int x=v[i][j],y=v[i][j+1];
            for(re int k=0;k<(1<<7);++k){
                if((k&(1<<(y-1)))){
                    dp[i][k]=max(dp[i][k],max(dp[x-1][k],dp[x-1][(1<<(y-1))^k])+pos[i]-pos[x]);
                }
            }
        }
    }
    re int ans=0;
    for(re int i=0;i<(1<<7);++i)if(__builtin_popcount(i)==m)ans=max(ans,dp[cnt][i]);
    if(ans)printf("%d",ans);else puts("-1");
}