[BalticOI 2019 Day2] 汤姆的餐厅

题目背景

译自 BalticOI 2019 Day2 T1. Tom's Kitchen

题目描述

Tom's Kitchen 是一家非常受欢迎的餐厅，其受欢迎的原因之一是每份菜都由至少 $ K $ 名厨师进行准备。今天有 $ N $ 份菜需要准备，第 $ i $ 份菜的准备时间是 $ A_i $ 小时。

Tom 可以雇佣 $ M $ 名厨师，厨师 $ j $ 最多可以工作 $ B_j $ 小时。此外，即使厨师 $ j $ 的工作时间不到 $ B_j $ 小时，他也会得到工作 $ B_j $ 小时的报酬。一名厨师可以花不同的时间准备不同的菜，但是每一道菜都需要由至少 $ K $ 名厨师准备，并且他们花的时间总和恰好为 $ A_i $。当一名厨师准备菜品时，他总会花正整数小时。

Tom 需要一套最优的雇佣厨师方案，以使得厨师不工作就获得报酬的小时数（即所有雇佣厨师的总工作时间上限与准备所有菜的总时间之差）尽可能小。

输入格式

第一行包含三个正整数：$ N,M,K $。

第二行包含 $ N $ 个整数 $ A_i $，第三行包含 $ M $ 个整数 $ B_j $。

输出格式

如果不存在一套方案可以完成所有菜的准备工作，输出 Impossible。否则输出一个整数，代表厨师不工作就获得报酬的小时数的最小值。

样例 #1

样例输入 #1

1 2 2
5
3 4

样例输出 #1

样例 #2

样例输入 #2

1 1 2
5
5

样例输出 #2

Impossible

样例 #3

样例输入 #3

3 3 3
3 3 2
3 3 3

样例输出 #3

Impossible

提示

样例解释 1

Tom 需要雇佣这两位厨师来完成所有菜的准备工作。准备所有菜的时间为 $ 5 $ 小时，但 Tom 需要支付 $ 3+4=7 $ 小时的费用，即厨师不工作就能得到 $ 2 $ 小时的工资。

样例解释 2

准备一份菜需要至少两位厨师，但只能雇佣一位厨师，因此不能完成准备工作。

样例解释 3

第三份菜无法由三位厨师来准备，因为准备第三份菜的时间只有 $ 2 $ 小时（这意味着如果由三名厨师准备第三份菜的话，至少有一位厨师的准备时间是 $ 0 $ 小时，而这是不符合题目要求的）。

子任务

各子任务的分值与数据规模如下：

子任务 1（9 分）：$ 1 \leq N,K \leq 300, 1 \leq M \leq 2, 1 \leq A_i,B_j \leq 300 $；
子任务 2（22 分）：$ 1 \leq N,K \leq 300, 1 \leq M \leq 15, 1 \leq A_i,B_j \leq 300 $；
子任务 3（20 分）：$ 1 \leq N,M,A_i,B_j \leq 300, K=1 $；
子任务 4（21 分）：$ 1 \leq N,M,K,A_i,B_j \leq 40 $；
子任务 5（28 分）：$ 1 \leq N,M,K,A_i,B_j \leq 300 $。

解题思路

参考题目提供者写的题解，已经写得非常好了。

首先如果存在某个 $a_i < k$ 显然无解，因为做这道菜的厨师至少消耗 $1$ 单位时间，而这道菜又至少需要 $k$ 个厨师，因此必须有 $a_i \geq k$。

假设选择的厨师的集合是 $S$，若这个方案合法首先必须有 $\sum\limits_{i \in S}{b_i} \geq \sum\limits_{i=1}^{n}{a_i}$，同时还要保证每道菜都至少有 $k$ 个厨师参与。这个感觉挺难想到如何去表示的，也不是很理解。

由于每道菜至少有 $k$ 个厨师参与，因此把一道菜的时间分成 $k$ 和剩余的 $a_i - k$，那么参与这道菜的厨师最多可以贡献 $1$ 单位时间（对于 $k$ 这部分而言），共至少需要 $n \times k$ 这么多的贡献。而一个厨师最多可以贡献 $\min\{ b_i, n \}$ 个单位的时间（即最多可以参与这么多不同的菜），因此需要满足 $\sum\limits_{i \in S}{\min\{ b_i, n \}} \geq n \times k$。

考虑 dp，定义状态 $f(i,j)$ 表示从前 $i$ 个厨师中选出总工作时间恰好为 $j$ 的所有方案中贡献的最大值。根据是否选择第 $i$ 个厨师进行状态划分（01 背包问题），有状态转移方程 $$f(i,j) = \max\{ f(i-1,j), \, f(i-1, j-b_i) + \min\{ b_i, n \} \}$$

最终答案就是从满足 $\sum\limits_{i=1}^{n}{a_i} \leq j \leq \sum\limits_{i=1}^{m}{b_i}$ 的 $j$ 中，找到满足 $f(m,j) \geq n \times k$ 的最小的 $j$。

AC 代码如下，时间复杂度为 $O(m \sum{b_i})$：

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

const int N = 310;

int a[N], b[N];
int f[N * N];

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    int sa = 0, sb = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        sa += a[i];
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d", b + i);
        sb += b[i];
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] < k) {
            printf("Impossible");
            return 0;
        }
    }
    memset(f, -0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = sb; j >= b[i]; j--) {
            f[j] = max(f[j], f[j - b[i]] + min(b[i], n));
        }
    }
    int ret = 1e9;
    for (int i = sa; i <= sb; i++) {
        if (f[i] >= n * k) ret = min(ret, i - sa);
    }
    if (ret == 1e9) printf("Impossible");
    else printf("%d", ret);
    
    return 0;
}