题解 P4890 【Never·island】

· · 题解

月赛的时候有事没考……后来才看到这题出的超棒！手动膜zcy……

刚开始以为是一个网络流模型，然后建模建了十几分钟没成功……后来猛然间想到离散化之后分类讨论线段端点似乎可行。

考虑到我们只需要求出关门的最长时间即可。于是可以给每个考察队建一个带权点，然后进行如下操作：

1.一个线段左边为起点，右边为终点。如果这两个点同属于一个考察队，那么就给该点权加上当前线段长度，表示如果给该考察队钥匙可以获得的贡献；否则就在分属的两个考察队之间连一条权值为线段长度的边，表示如果给这两个考察队钥匙可以获得的贡献。

2.一个线段左边和右边都是起点，则给左边的考察队点权加上线段长度，原因同上；

3.一个线段左边和右边都是终点，则给右边的考察队点权加上线段长度；

4.一个线段左边是终点，右边是起点，则必然给答案造成贡献，直接给答案加上贡献即可。

接下来我想着这个图懵了一会儿，怎么求解从中选k个点使得诱导子图的权值和最大？刚开始想着这个图是个二分图，可以怎么做；后来猛然发现这个图实际上是由很多链组成的……

于是就很显然了，对于每条链都dp一下，dp[i][j][0/1]就表示当前dp到了前i个点，选j个点，当前点是否选择的最大值，这个dp是很easy的，于是问题就在O(n^2)的时间内解决了。

再次膜出题人Orz……/菜鸡的我刚开始连dp的初始值都没赋2333

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2005;
map<int, int> mp;
int srt[maxn * 2], f[maxn][maxn][2], val[maxn], ss[maxn];
int vis[maxn], nxt[maxn], ord[maxn], tot, n, m;
void dfs(int u){
    vis[ord[++tot] = u] = 1;
    if(nxt[u]) dfs(nxt[u]);
}
int main(){
    freopen("input.txt", "r", stdin);
    freopen("out1.txt", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        int l, r;
        scanf("%d%d", &l, &r);
        mp[l] = i * 2;
        mp[r] = i * 2 + 1;
        srt[i] = l;
        srt[i + n] = r;
    }
    sort(srt + 1, srt + n + n + 1);
    int res = 0;
    for(int i = 1; i < n + n; i++){
        int l = srt[i], r = srt[i + 1];
        int ld = mp[l], rd = mp[r];
        if((ld & 1) && !(rd & 1)) res += r - l;
        if((ld & 1) && (rd & 1)) val[rd >> 1] += r - l;
        if(!(ld & 1) && !(rd & 1)) val[ld >> 1] += r - l;
        if(!(ld & 1) && (rd & 1)){
            if((ld >> 1) == (rd >> 1)) val[ld >> 1] += r - l;
            else nxt[rd >> 1] = ld >> 1, ss[rd >> 1] = r - l;
        }
    }
    for(int i = 1; i <= n + n; i++){
        int d = mp[srt[i]];
        if(!(d & 1) && !vis[d >> 1]) dfs(d >> 1);
    }
    //for(int i = 1; i <= n; i++) printf("%d ", ord[i]);
    memset(f, 0xbf, sizeof(f));
    f[n + 1][0][0] = 0;
    for(int i = n; i > 0; i--){
        f[i][0][0] = 0;
        for(int j = min(n - i + 1, m); j > 0; j--){
            f[i][j][0] = max(f[i + 1][j][0], f[i + 1][j][1]);
            if(!nxt[ord[i]]) f[i][j][1] = max(f[i + 1][j - 1][0], f[i + 1][j - 1][1]) + val[ord[i]];
            else f[i][j][1] = max(f[i + 1][j - 1][0], f[i + 1][j - 1][1] + ss[ord[i]]) + val[ord[i]];
        }
    }
    printf("%d\n", srt[n + n] - srt[1] - res - max(f[1][m][0], f[1][m][1]));
    return 0;
}