跳转至

黑心工厂

题意

黑心工厂有 n 名工人和 p 条流水线。第 i 名工人会在 [s_i,t_i] 时间段内工作。

每名工人必须被分配到一条流水线。流水线工作的时间是所有工人工作时间的交集，且需保证没有流水线工作时间为 0。求所有流水线的最大工作时间总和。

解析

考虑两名工人 i,j 满足 s_i\le s_j\le t_j\le t_i。至少存在一种最优解，i 要么和 j 属于同一流水线，要么独自属于一条只有一人的流水线。

证明

若 i 与 j 属于不同的流水线，且 i 的流水线中还有其它的工人，则将 i 调往 j 的流水线后，i 原本所在的流水线工作时间不会变短，j 所在的流水线工作时间不变。

因此只要存在一种最优解满足 i 和 j 不属于同一流水线，且 i 所在流水线还有其它工人，就一定存在另一种最优解满足 i 和 j 属于同一流水线。

我们将所有工人分为两个集合 S 和 T：对于 S 中所有工人 i 都存在一个工人 j 满足 s_i\le s_j \le t_j \le t_i，而 T 是 S 关于全集的补集。根据上面的结论，S 中的工人要么被独自分配到一条流水线，要么不产生任何影响。我们可以轻松求出 S 中产生 i 条流水线的最大工作时间。

对于集合 T，我们将工人以 s 为第一关键字，t 为第二关键字排序，由于工人互不相交，则有 s_1\le s_2\le \ldots s_{|T|} 以及 t_1\le t_2\le \ldots t_{|T|}。对于任意 i 都存在至少一个将 T 分为 i 条流水线的最优解，每条流水线包含的工人都是相邻的。

证明

若在某个最优解中存在 i<j<k 满足 i 与 k 在同一流水线，而 j 在另一条流水线，则

  • 若 j 所在流水线只有 j 一人，则将 j 加入 i 所在流水线，使 k 离开 i 所在流水线并单独成立一条流水线，一定能够得到更长的工作时间
  • 若 j 所在流水线不止 j 一人，则将 j 加入 i 所在流水线一定不会使这条流水线的工作时间更短。

这样不断调整一定能得到一个所有在同一流水线上的工人都是相邻的最优解。

于是可以通过动态规划求出 T 的答案，然后与 S 的答案合并即可。

实现

#include <bits/stdc++.h>

const int maxn = 2e2 + 19;

bool vist[maxn];
std::pair<int, int> a[maxn], st[maxn];
int top;

int n, p, dp[maxn][maxn], s[maxn];

int main(){
    std::scanf("%d%d", &n, &p);
    for(int i = 1; i <= n; ++i) std::scanf("%d%d", &a[i].first, &a[i].second);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(j != i && a[i].first <= a[j].first && a[i].second >= a[j].second && a[i].second - a[i].first > a[j].second - a[j].first){
                vist[i] = true;
                break;
            }

    for(int i = 1; i <= n; ++i)
        if(!vist[i])
            st[++top] = a[i];
    std::sort(st + 1, st + 1 + top);

    std::memset(dp, -0x3f, sizeof dp), dp[0][0] = 0;    
    for(int k = 1; k <= p; ++k)
        for(int i = 1; i <= n; ++i)
            for(int j = 0; j < i; ++j)
                if(st[j + 1].second > st[i].first)
                    dp[i][k] = std::max(dp[i][k], dp[j][k - 1] + st[j + 1].second - st[i].first);

    top = 0;
    for(int i = 1; i <= n; ++i)
        if(vist[i])
            s[++top] = a[i].second - a[i].first;
    std::sort(s + 1, s + 1 + top, std::greater<int>());
    for(int i = 1; i <= top; ++i) s[i] += s[i - 1];

    int ans = 0;
    for(int i = 1; i <= p; ++i)
        ans = std::max(ans, dp[n - top][i] + s[p - i]);
    std::printf("%d\n", ans);

    return 0;
}

来源

NOI.AC #2016 T1

评论