bzoj2436: [Noi2011]Noi嘉年华 | jeffswt: the ac moments

Description

NOI2011 在吉林大学开始啦! 为了迎接来自全国各地最优秀的信息学选手, 吉林大学决定举办两场盛大的 NOI 嘉年华活动, 分在两个不同的地点举办. 每个嘉年华可能包含很多个活动, 而每个活动只能在一个嘉年华中举办. 现在嘉年华活动的组织者小安一共收到了 \(n\) 个活动的举办申请, 其中第 \(i\) 个活动的起始时间为 \(S_i\), 活动的持续时间为 \(T_i\). 这些活动都可以安排到任意一个嘉年华的会场, 也可以不安排. 小安通过广泛的调查发现, 如果某个时刻, 两个嘉年华会场同时有活动在进行 (不包括活动的开始瞬间和结束瞬间), 那么有的选手就会纠结于到底去哪个会场, 从而变得不开心. 所以, 为了避免这样不开心的事情发生, 小安要求不能有两个活动在两个会场同时进行 (同一会场内的活动可以任意进行). 另外, 可以想象, 如果某一个嘉年华会场的活动太少, 那么这个嘉年华的吸引力就会不足, 容易导致场面冷清. 所以小安希望通过合理的安排, 使得活动相对较少的嘉年华的活动数量最大. 此外, 有一些活动非常有意义, 小安希望能举办, 他希望知道, 如果第 \(i\) 个活动必须举办 (可以安排在两场嘉年华中的任何一个), 活动相对较少的嘉年华的活动数量的最大值.

Input

输入的第一行包含一个整数 \(n\), 表示申请的活动个数. 接下来 \(n\) 行描述所有活动, 其中第 \(i\) 行包含两个整数 \(S_i, T_i\), 表示第 \(i\) 个活动从时刻 \(S_i\) 开始, 持续 \(T_i\) 的时间.

Output

输出的第一行包含一个整数, 表示在没有任何限制的情况下, 活动较少的嘉年华的活动数的最大值. 接下来 \(n\) 行每行一个整数, 其中第 \(i\) 行的整数表示在必须选择第 \(i\) 个活动的前提下, 活动较少的嘉年华的活动数的最大值.

Sample Input

Sample Output

Data Range

对于所有数据, 满足:\(1 \leq n \leq 200, 0 \leq S_i \leq 10^9, 1 \leq T_i \leq 10^9\)

Explanation

题解已经写的很清楚了, 原文链接:http://blog.csdn.net/clover_hxy/article/details/52214506

先将区间离散, 时间就全是 \(O(n)\) 级别的了.

预处理 \(sum[i][j]\) 表示 \(i\) 到 \(j\) 时间有多少个活动.

设 \(f[i][j]\) 表示到第 \(i\) 时间为止, 第一个场地已经举办了 \(j\) 场活动时第二个场地最多举办多少场活动.

\(f[i][j]=max\{f[i-1][j],f[k][j]+sum[k+1][i],f[k][j-sum[k+1][i]]\}\) 分别表示 \(sum[k+1][i]\) 这一段的活动不演出, 在第二个场地演出, 在第一个场地演出, 复杂度 \(O(n^3)\)

再用同样的方法求 \(g[i][j]\) 表示倒序时间到 \(i\) 时, 第一个场地举办了 \(j\) 个活动时第二个场地最多举办多少个活动.

设 \(dp[i][j]\) 表示 \(i-j\) 这一段所有的活动同时选到某一个场地的最大答案.

\(dp[i][j]=max\{dp[i][j],min\{max(f[i-1][x]+g[j+1][y],x+y\},min\{f[i-1][x]+g[j+1][y],x+y\}+sum[i][j]\}\) 表示把 \(sum[i][j]\) 这一段给一二场地中较小的一个场地, 再更新答案. 这样直接暴力 \(O(n^4)\)

但是随着 \(x\) 的增加 \(y\) 是单调不降的, 所以最终的时间复杂度是 \(O(n^3)\)

Source Code


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

#define maximize(__x,__y) __x=max(__x,__y)
using namespace std;
typedef long long lli;
const int maxn = 1010;
const int infinit = 0x3fffffff;

struct srtr { int type, val, id, uuid; };
bool operator < (srtr a, srtr b) {
    return a.val < b.val; }

int n, m;
srtr srt[maxn];
int l[maxn], r[maxn];
int sum[maxn][maxn];
int f[maxn][maxn], g[maxn][maxn], dp[maxn][maxn];
int res_idv[maxn];

int calc_dp(int i, int j, int x, int y)
{
    if (f[i-1][x] < 0 || g[j+1][y] < 0)
        return -infinit;
    return min(max(x+y, f[i-1][x] + g[j+1][y]),
        min(x+y, f[i-1][x] + g[j+1][y]) + sum[i][j]);
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    // Create distinct input through s, t.
    int t_cnt = 0;
    for (int i = 1, s, t; i <= n; i++) {
        scanf("%d%d", &s, &t);
        srt[++t_cnt].type = 1, srt[t_cnt].val = s, srt[t_cnt].id = i;
        srt[++t_cnt].type = 0, srt[t_cnt].val = s+t-1, srt[t_cnt].id = i;
    }
    sort(srt + 1, srt + 1 + t_cnt);
    srt[0].val = -1;
    m = 0;
    for (int i = 1; i <= 2*n; i++) {
        m += srt[i].val != srt[i-1].val;
        srt[i].uuid = m;
    }
    for (int i = 1; i <= 2*n; i++)
        (srt[i].type ? l : r)[srt[i].id] = srt[i].uuid;
    // Finished distinction of time.
    // The total timestamps is stored in "m".
    // Retrieving contiguous events among time i through j.
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 1; k <= n; k++)
                if (l[k] >= i && r[k] <= j)
                    sum[i][j] += 1;
    // Directives from left -> right
    memset(f, 128, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= m; i++)
        for (int j = 0; j <= n; j++) {
            f[i][j] = f[i-1][j];
            for (int k = 0; k <= i-1; k++) {
                maximize(f[i][j], f[k][j] + sum[k+1][i]);
                if (j - sum[k+1][i] >= 0)
                    maximize(f[i][j], f[k][j - sum[k+1][i]]);
            }
        }
    // Directives from right -> left
    memset(g, 128, sizeof(g));
    g[m+1][0] = 0;
    for (int i = m; i >= 1; i--)
        for (int j = 0; j <= n; j++) {
            g[i][j] = g[i+1][j];
            for (int k = m+1; k > i; k--) {
                maximize(g[i][j], g[k][j] + sum[i][k-1]);
                if (j - sum[k-1][i] >= 0)
                    maximize(g[i][j], g[k][j - sum[i][k-1]]);
            }
        }
    // Resolving contigencies between intervals
    for (int i = 1; i <= m; i++)
        for (int j = i; j <= m; j++)
            if (sum[i][j] > 0) {
                int y = n;
                for (int x = 0; x <= n; x++) {
                    int best = calc_dp(i, j, x, y);
                    while (y > 0) {
                        int tmp = calc_dp(i, j, x, y-1);
                        if (tmp >= best)
                            best = tmp, y -= 1;
                        else break;
                    }
                    maximize(dp[i][j], best);
                }
            }
    // Final results, processing.
    int res = 0;
    for (int i = 1; i <= n; i++)
        maximize(res, min(i, g[1][i]));
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= m; i++)
            for (int j = i; j <= m; j++)
                if (l[k] >= i && r[k] <= j)
                    maximize(res_idv[k], dp[i][j]);
    // Output results
    printf("%d\n", res);
    for (int i = 1; i <= n; i++)
        printf("%d\n", res_idv[i]);
    return 0;
}