[NOI 2011]NOI 嘉年华

Description

给你 \(n\) 个区间，让你选出其中一些分为两组，要求两组区间不能有交集，组内可以有交集。让你最大化两组之间区间个数较小的那一组的选取区间个数。以及对于每个区间 \(i\)，回答第 \(i\) 个区间必选（放在第一组或者第二组），两组个数的最小值的最大值。

\(1\leq n\leq 200\)

Solution

首先，可以知道每组一定是若干个连续的时间段组成的。那么我们可以按时间来 DP，先离散化，设时间上限为 \(T\)。

为了方便转移，我们记 \(cnt_{i,j}\) 为全在 \([i,j]\) 时间段内的区间个数。这个是可以在 \(O(n^3)\) 内预处理出来的。

记 \(f_{i,j}\) 表示 \(1\sim i\) 时间段，第一组有 \(j\) 个区间时第二组最多有多少个区间。首先，若 \(i\) 这个时刻不选，可以继承 \(i-1\) 时刻的状态，那么赋值 \(f_{i,j}=f_{i-1},j\)。

考虑转移就是枚举以 \(i\) 为右端点，\(k\) 为左端点，这一整个时间段放在第一组或是第二组，显然对于每个 \(k\)，\(f_{i,j}=\max\{f_{k-1,j}+cnt_{k,i},f_{k-1,j-cnt_{k,i}}\}\)。

那么第一问的答案显然就是 \(\max\limits_{0\leq i\leq n}\min\{i,f_{T,i}\}\)。

考虑第二问，首先我们仿照 \(f\) 的定义用相同的方式 DP 出一个数组 \(g\)，表示 \(i\sim T\) 时间段，第一组有 \(j\) 个区间时第二组最多有多少个区间。

那么对于第 \(i\) 个区间，因为它必须被选，那么去考虑选择哪些时间段是包含第 \(i\) 个区间的。用 \(O(n^2)\) 去枚举端点 \([l,r]\)，另外考虑 \(1\sim l-1\) 中放 \(a\) 个在第一组，\(r+1\sim T\) 中放 \(b\) 个在第一组。考虑 \([l,r]\) 放在第一组还是第二组，显然答案就是 \(\max\limits_{l,r,a,b}\{\min\{f_{l-1,a}+g_{r+1,b}+cnt_{l,r}, a+b\}, \min\{f_{l-1,a}+g_{r+1,b}, a+b+cnt_{l,r}\}\}\)。不过这样，单个询问就是 \(O(n^4)\) 的，吃不消。

容易发现上述计算时会有许多冗余重复的计算，那么我们考虑预处理一个数组 \(dp_{i,j}\) 表示 \([i,j]\) 区间必选，最大化最小区间个数的值。

显然对于每个 \(i,j\)，我们只需枚举 \(1\sim i-1\) 中放在第一组个数 \(a\)，\(j+1\sim T\) 中放在第一组个数 \(b\)。不过预处理这个数组还是 \(O(n^4)\) 的。

值得注意的是 \(f_{i,j}\) 随 \(j\) 增大，\(f\) 值单调不增。利用这个单调性，可以双指针优化，枚举 \(a\) 时，继承 \(b\) 值。最终复杂度为 \(O(n^3)\)。

预处理完，之后只需 \(O(n^2)\) 枚举端点就可以计算答案了。

综上复杂度为 \(O(n^3)\)。

Code

#include <bits/stdc++.h>

#define inf (-f[N-1][N-1])

using namespace std;

const int N = 405;

int n, l, r, f[N][N], b[N], tot, cnt[N][N], g[N][N], dp[N][N];

struct tt {

    int l, r;

} a[N];

int main() {

    scanf("%d", &n);

    for (int i = 1; i <= n; i++)

        scanf("%d%d", &l, &r),

        b[++tot] = a[i].l = l, b[++tot] = a[i].r = l+r-1;

    sort(b+1, b+tot+1);

    tot = unique(b+1, b+tot+1)-b-1;

    for (int i = 1; i <= n; i++)

        a[i].l = lower_bound(b+1, b+tot, a[i].l)-b,

        a[i].r = lower_bound(b+1, b+tot, a[i].r)-b;

    for (int i = 1; i <= tot; i++)

        for (int j = i; j <= tot; j++)

            for (int k = 1; k <= n; k++)

                cnt[i][j] += (i <= a[k].l && a[k].r <= j);

    memset(f, 192, sizeof(f));

    memset(g, 192, sizeof(g));

    f[0][0] = 0;

    for (int i = 1; i <= tot; i++)

        for (int j = 0; j <= n; j++) {

            f[i][j] = f[i-1][j];

            for (int k = i; k >= 1; k--) {

                f[i][j] = max(f[i][j], f[k-1][j]+cnt[k][i]);

                if (j >= cnt[k][i]) f[i][j] = max(f[i][j], f[k-1][j-cnt[k][i]]);

            }

        }

    g[tot+1][0] = 0;

    for (int i = tot; i >= 1; i--)

        for (int j = 0; j <= n; j++) {

            g[i][j] = g[i+1][j];

            for (int k = i; k <= tot; k++) {

                g[i][j] = max(g[i][j], g[k+1][j]+cnt[i][k]);

                if (j >= cnt[i][k]) g[i][j] = max(g[i][j], g[k+1][j-cnt[i][k]]);

            }

        }

    int ans = -inf;

    for (int j = 0; j <= n; j++)

        ans = max(ans, min(j, f[tot][j]));

    printf("%d\n", ans);

    for (int i = 1; i <= tot; i++)

        for (int j = i; j <= tot; j++) {

            int l = cnt[1][i-1];

            for (int r = 0; r <= cnt[j+1][tot]; r++) {

                while (l && max(min(f[i-1][l]+g[j+1][r]+cnt[i][j], l+r), min(f[i-1][l]+g[j+1][r], l+r+cnt[i][j]))

                <= max(min(f[i-1][l-1]+g[j+1][r]+cnt[i][j], l-1+r), min(f[i-1][l-1]+g[j+1][r], l-1+r+cnt[i][j]))) --l;

                dp[i][j] = max(dp[i][j], max(min(f[i-1][l]+g[j+1][r]+cnt[i][j], l+r), min(f[i-1][l]+g[j+1][r], l+r+cnt[i][j])));

            }

        }

    for (int i = 1; i <= n; i++) {

        int ans = 0;

        for (int l = 1; l <= a[i].l; l++)

            for (int r = a[i].r; r <= tot; r++)

                ans = max(ans, dp[l][r]);

        printf("%d\n", ans);

    }

    return 0;

}

巴特西

[NOI 2011]NOI 嘉年华

Description

Solution

Code

最新文章

热门文章