题解 P3358 【最长k可重区间集问题】

Adove · 2018-03-18 19:23:46 · 题解

这题我用类似暴力的方法吸氧1376ms过了。

https://www.luogu.org/record/show?rid=6275933

思路：分层图最长路dfs+剪枝。

对于这n个区间，我们将其按左端点为关键字排序，复制k份，分为k层。

对于不重叠的两段区间，从左边区间连到同层右边的区间，边权为右边区间长；并从右边区间连到下层左边区间同位置的区间，边权为左边区间长

对于重叠的两段区间，点数过多时不连边，否则从左边连向下一层的右边区间，边权为右边线段长。

最后，另起源点s，连向第一层的各段区间，边权为各段区间长。

跑一遍分层图最长路，注意选过的区间不能再选。

上代码↓

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int INF=2e9;

int n,k,s,np,ans;
int h[1500005],ln[1500005],q[1500005];
bool boom[5005];
struct lint{
    int l,r;
}line[5005];
struct rpg{
    int li,nx,ln;
}a[1500005];

inline void add(int ls,int nx,int ln){
    a[++np]=(rpg){h[ls],nx,ln};
    h[ls]=np;
}

bool cmp(lint a,lint b){
    return a.l<b.l;
}

void dfs(int x){
    for(register int i=h[x];i;i=a[i].li){
        if(!boom[a[i].nx%n]&&ln[a[i].nx]<ln[x]+a[i].ln){
            ln[a[i].nx]=ln[x]+a[i].ln;
            boom[a[i].nx%n]=1;
            dfs(a[i].nx);
            boom[a[i].nx%n]=0;
        }
    }
}

int main(){
    scanf("%d%d",&n,&k);
    for(register int i=1;i<=n;++i){
        scanf("%d%d",&line[i].l,&line[i].r);
    }sort(line+1,line+n+1,cmp);
    for(register int i=1;i<=n;++i){
        add(s,i,line[i].r-line[i].l);
    }
    for(int l=0;l<k;++l){
        for(register int i=1;i<n;++i){
            for(int j=i+1;j<=n;++j){
                if(i!=j){
                    if(line[i].r<=line[j].l){
                        add(i+n*l,j+n*l,line[j].r-line[j].l);
                        add(j+n*l,i+n*(l+1),line[i].r-line[i].l);
                    }else if(n<400){
                        add(i+n*l,j+n*(l+1),line[j].r-line[j].l);
                    }
                }
            }
        }
    }dfs(s);
    for(register int i=n*(k-1);i<=n*k;++i)
        ans=max(ln[i],ans);
    printf("%d\n",ans);
    return 0;
}