BZOJ 1107 - [POI2007]驾驶考试egz

#动态规划 #最长上升子序列
Published on 2016-09-16

题目地址

描述

成都的驾驶考试在一个有 n(1≤n≤100000)n(1\le n\le 100000) 条平行的自南向北的单向的道路的场地中进行。每条道路长度为 m(1≤m≤100000)m(1\le m\le 100000) 米，并且都在同一条水平线上开始和结束。街道从西向东分别编号为 11 到 nn。同样有 p(1≤p≤100000)p(1\le p\le 100000) 条单向的自西向东或自东向西的街道垂直于上面描述的街道，每一条这样的街道链接了两个相邻的自南向北的道路。当然自西向东和自东向西的道路可以重叠，那就是一个双向的街道了。

考生选择一个自南向北的道路作为他考试的起始点和另外一个自南向北的道路作为他考试的终止点。他们的考试项目是将车从开始的道路驾驶到作为终止点的道路。考生们总是选择一个可以到达所有其他街道的起始道路作为开始点。现在，考们总是感到十分无趣因为他们只有很少的起始道路可以选择，所以教练们决定改造先有的考试场所，由于经费的限制，他们决定添加至多 K(1≤K≤100000)K(1\le K\le 100000) 条东西向的道路，使得能够选择的起始道路尽量地多。

分析

如果不进行转换，这个题目看起来像是一个 DP，但是怎么样搞都是没办法，原因是——入手的方向错了。

引理一：从一条道路出发能够到达所有道路的充分必要条件是从这条道路出发能够到达最左边和最右边的道路。

证明：由于自东向西道路只连接两个相邻的道路，所以如果能到达最左边和最右边，那么必然经过了所有的道路，也就能够到达所有的道路。

引理二：将所有的道路反向（不仅仅是自东向西的道路，自南向北的道路也需要反向），从一条道路出发能够到达所有道路的充分必要条件是从最左边的道路和最右边的道路出发都能够到达这条道路。

证明：根据引理一，容易证明。

现在我们成功的将从每条道路出发转换为了从最左最右道路出发，这样就有一个 DP 的模型了。

设 fif_i 为从最左边的道路，到达第 ii 条道路所需添加的道路条数，gig_i 为从最右边的道路，到达第 ii 条道路所需添加的道路条数。求出这两个量，用一下单调队列就可以算出答案，我们考虑求 fif_i：

我们发现，反向后，如果有一条 0→i0\rightarrow i 的道路，那么每次的中转点（横向边）的高度是单调不增的，也就是说我们要补出一个单调不增的中转点高度的序列，这其实就是 LIS，我们求出 0→i0\rightarrow i 的 LIS 为 ll，那么需要补 i−li - l 条边。

最后还有一个问题，同一条竖直道路上的所有中转点，是只能计算一次 LIS 的贡献的（也就是说一个 LIS 中不能有同一条道路上的两个中转点），很简单，两个解决方案：

  1. 去除重复道路，从大到小计算贡献。
  2. 每次计算贡献以后不修改，算完了以后再一起修改。

本代码采用第二种方案。

复杂度： O(nlogn)O(n\log n)。

代码

//  Created by Sengxian on 09/14/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1107 LIS
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 100000 + 3, MAX_P = 100000 + 3, INF = 0x3f3f3f3f;
int n, m, p, K, f[MAX_N], g[MAX_N];

struct node {
    node *next;
    int w;
    node(node *next, int w): next(next), w(w) {}
    node() {}
}pool[MAX_P], *pit = pool, *F[MAX_N], *G[MAX_N];

int LIS(int f[MAX_N], node *F[MAX_N]) {
    static int dp[MAX_N], t[MAX_N];
    memset(dp, 0x3f, sizeof dp);
    f[0] = 0;
    for (int i = 1, j = 0; i < n; ++i) {
        j = 0;
        for (node *cur = F[i]; cur; cur = cur->next, ++j)
            t[j] = upper_bound(dp, dp + n, cur->w) - dp;
        j = 0;
        for (node *cur = F[i]; cur; cur = cur->next, ++j)
            dp[t[j]] = min(dp[t[j]], cur->w);
        f[i] = i - (lower_bound(dp, dp + n, INF) - dp);
    }
    for (int i = n - 1; i >= 0; --i)
        if (f[i] == 0) return i;
    return 0;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), m = ReadInt(), p = ReadInt(), K = ReadInt();
    for (int i = 0, _n, _m, _d; i < p; ++i) {
        _n = ReadInt() - 1, _m = -ReadInt(), _d = ReadInt();
        if (_d == 1) {
            F[_n + 1] = new(pit++) node(F[_n + 1], _m);
        } else if (_d == 0) {
            G[n - 1 - _n] = new(pit++) node(G[n - 1 - _n], _m);
        } else assert(false);
    }
    int a = LIS(f, F), b = LIS(g, G), ans = 0;
    for (int i = 0, j = n - 1; i < n; ++i) {
        if (f[i] > K) break;
        while (j - 1 >= 0 && f[i] + g[j] > K) --j;
        ans = max(ans, i - (n - 1 - j) + 1);
    }
    printf("%d\n", ans - max(0, (a - (n - 1 - b) + 1)));
    return 0;
}
Codeforces 715B - Complete The Graph