[Luogu P4890] Never·island

Luogu P4890

思路

将所有线段端点排一下序,然后对于某一截线段,可以分以下四种情况:

  1. 左端点是出发,右端点是回来。假如两个端点属于属于同一队,那么就将代表这一队的点的点权加上线段长度。假如两个端点不属于同一队,那么就将代表两个队的点间连一条边,边权是线段长度
  2. 两个端点都是出发,那么就将左端点代表的队的点权加上线段长度
  3. 两个端点都是到达,那么就将右端点代表的队的点权加上线段长度
  4. 左端点是到达,右端点是出发,直接找个变量累计上线段长度

之后dp找出不超过$K$个点的诱导子图,使得点权+边权最大,那么答案就是最左边和最右边的点的距离减去点权+边权减去累计起来的线段长度

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

template <typename T> void in(T &_){
    char c=getchar(); _=0; int fl=1;
    while(c<'0'||c>'9') fl=c=='-'?-1:fl, c=getchar();
    while(c>='0'&&c<='9') _=_*10+c-'0', c=getchar(); _*=fl;
}

struct Data{int pos, id, opt;}a[4010];
int N, K, f[2010][2010][2], val[2010], deg[2010], ans, q[2010], ve[2010], top;
bool vis[2010];
struct Graph{
    int to[100010], ne[100010], v[100010], head[2010], cnt;
    Graph() : cnt(0){}
    inline void add_edge(int x, int y, int z){
        to[++cnt]=y; ne[cnt]=head[x]; head[x]=cnt; v[cnt]=z;
        to[++cnt]=x; ne[cnt]=head[y]; head[y]=cnt; v[cnt]=z;
        deg[x]++; deg[y]++;
    }
    inline int operator [](int x){return head[x];}
}G;

void dfs(int x, int fa){
    q[++top]=x; vis[x]=true;
    for(int i=G[x]; i; i=G.ne[i]) if(G.to[i]!=fa){
        ve[top]=G.v[i]; dfs(G.to[i], x);
    }
}

int main(){
    in(N); in(K);
    for(int i=1; i<=N; i++){
        in(a[i].pos); in(a[i+N].pos);
        a[i].id=a[i+N].id=i;
        a[i].opt=1; a[i+N].opt=0;
    }
    std::sort(a+1, a+2*N+1, [](Data x, Data y){return x.pos<y.pos;});
    for(int i=1; i<2*N; i++){
        int dis=a[i+1].pos-a[i].pos;
        if(a[i].opt && !a[i+1].opt){
            if(a[i].id==a[i+1].id) val[a[i].id]+=dis;
            else G.add_edge(a[i].id, a[i+1].id, dis);
        }else if(a[i].opt && a[i+1].opt)
            val[a[i].id]+=dis;
        else if(!a[i].opt && !a[i+1].opt)
            val[a[i+1].id]+=dis;
        else
            ans+=dis;
    }
    for(int i=1; i<=N; i++) if(deg[i]<=1 && !vis[i])
        dfs(i, 0);
    memset(f, -0x3f, sizeof(f));
    f[1][0][0]=0; f[1][1][1]=val[q[1]];
    for(int i=2; i<=N; i++)
        for(int j=0; j<=K; j++){
            if(j){
                f[i][j][1]=std::max(f[i][j][1], f[i-1][j-1][0]+val[q[i]]);
                f[i][j][1]=std::max(f[i][j][1], f[i-1][j-1][1]+val[q[i]]+ve[i-1]);
            }
            f[i][j][0]=std::max(f[i][j][0], std::max(f[i-1][j][0], f[i-1][j][1]));
        }
    int mx=-0x3f3f3f3f;
    for(int i=0; i<=K; i++)
        mx=std::max(mx, std::max(f[N][i][0], f[N][i][1]));
    printf("%d\n", a[2*N].pos-a[1].pos-mx-ans);
    return 0;
}
标签:

发表评论

电子邮件地址不会被公开。 必填项已用*标注