题解

思路分析

这是一道 二分答案 + DP + 贪心 的任务调度优化问题。

问题建模

• $P$ 个计算节点处理 $A$ 个 A 类任务和 $B$ 个 B 类任务
• 每个节点有启动时间和计算时间（随任务数平方增长）
• 目标：最小化最后完成的节点的完成时间

核心思路

1. 二分答案

二分最大完成时间 $mid$，判断能否在时间 $mid$ 内完成所有任务。

2. DP 判断可行性

对于固定的 $mid$，判断每个节点能处理的任务组合。

定义 $f[i][a][b][last]$ 表示节点 $i$ 处理 $a$ 个 A 类任务、$b$ 个 B 类任务，上一个任务类型为 $last$（0=A, 1=B），所需的最小时间。

状态转移：

• 从 $f[i][a-x][b][1]$ 转移：先做 B 类，再做 $x$ 个 A 类$$f[i][a][b][0] = f[i][a-x][b][1] + t_i^A + k_i^A \cdot x^2 $$
• 从 $f[i][a][b-y][0]$ 转移：先做 A 类，再做 $y$ 个 B 类$$f[i][a][b][1] = f[i][a][b-y][0] + t_i^B + k_i^B \cdot y^2 $$

3. 背包DP分配任务

定义 $g[i][a]$ 表示前 $i$ 个节点处理了 $a$ 个 A 类任务后，最多能处理多少 B 类任务。

对于每个节点 $i$，枚举它能处理的 $(x, y)$ 组合（满足 $f[i][x][y][\cdot] \leq mid$）：

4. 判断可行性

如果 $g[P][A] \geq B$，说明在时间 $mid$ 内能完成所有任务。

算法步骤

1. 预处理每个节点的时间函数：

   • 对每个节点 $i$，预处理 $f[i][a][b][last]$

2. 二分答案：

   • 二分时间 $mid$
   • 使用 DP 判断可行性

3. 背包DP验证：

   • 枚举节点和任务分配
   • 判断是否满足 $g[P][A] \geq B$

4. 输出答案

复杂度分析

• 预处理：$O(P \cdot A \cdot B)$
• 二分：$O(\log T)$
• DP验证：$O(P \cdot A \cdot B)$
• 总时间复杂度：$O(P \cdot A \cdot B \cdot \log T)$
• 空间复杂度：$O(P \cdot A \cdot B)$

#include <bits/stdc++.h>

using namespace std;

const int MAX_P = 20 + 5;
const int MAX_A = 60 + 5;
const int INF32 = 1e9;

int A, B, P;
int f[MAX_P][MAX_A][MAX_A][2];
int g[MAX_P][MAX_A];

int main() {
    scanf("%d%d%d", &A, &B, &P);
    for (int i = 1; i <= P; i ++) {
        int ta, tb, ka, kb;
        scanf("%d%d%d%d", &ta, &tb, &ka, &kb);
        for (int a = 0; a <= A; a ++) {
            for (int b = 0; b <= B; b ++) {
                if (a + b == 0) continue;
                f[i][a][b][0] = INF32;
                f[i][a][b][1] = INF32;
                for (int x = 1; x <= a; x ++) {
                    f[i][a][b][0] = min(f[i][a][b][0], f[i][a - x][b][1] + ta + ka * x * x);
                }
                for (int y = 1; y <= b; y ++) {
                    f[i][a][b][1] = min(f[i][a][b][1], f[i][a][b - y][0] + tb + kb * y * y);
                }
                // printf("f[%d][%d][%d]=%d,%d\n", i, a, b, f[i][a][b][0], f[i][a][b][1]);
            }
        }
        // printf("\n");
    }
    int l = 0, r = INF32;
    while (l < r) {
        int mid = l + r >> 1;
        for (int a = 0; a <= A; a ++) {
            g[0][a] = -INF32;
        }
        g[0][0] = 0;
        for (int i = 1; i <= P; i ++) {
            for (int a = 0, b; a <= A; a ++) {
                g[i][a] = g[i - 1][a];
            }
            for (int x = 0; x <= A; x ++) {
                int y = B;
                for (; y >= 0 && f[i][x][y][0] > mid && f[i][x][y][1] > mid; y --);
                // printf("i=%d,x=%d,y=%d\n", i, x, y);
                if (y >= 0) {
                    for (int a = 0; a <= A; a ++) {
                        g[i][a] = max(g[i][a], g[i - 1][a - x] + y);
                    }
                }
            }
            // for (int a = 0; a <= A; a ++) {
            //     printf("g[%d][%d]=%d\n", i, a, g[i][a]);
            // }
        }
        // printf("mid=%d g[P][A]=%d\n", mid, g[P][A]);
        if (g[P][A] >= B) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    printf("%d\n", l);
    return 0;
}

题解

把问题理解成“给定一个截止时间 $T$，能否在不超过 $T$ 的时间内完成全部 $A$ 类、$B$ 类子任务”。如果我们可以判定这一命题是否成立，再对 $T$ 二分即可。

对每个计算节点单独做 DP，预先算出 f[i][a][b][last]：表示第 i 个节点连续执行 $a$ 个 $A$ 子任务和 $b$ 个 $B$ 子任务，并以 last 指示的类型结束时所需的最短时间。状态转移十分直接：加一个同类型任务就是在当前时间基础上累加 $t + k \times x^2$ 这样的公式，加一个不同类型任务需要强制切换工作模式（用另一个 last）。由于 $n_A, n_B \le 60$，这个 DP 的规模可以接受。

随后对答案进行二分。给定猜测的时间上限 mid，我们再做一次类似背包的 DP：g[i][a] 表示使用前 $i$ 个节点，最多可以完成多少个 $B$ 任务，同时恰好完成 $a$ 个 $A$ 任务。枚举当前节点分配到的 $x$ 个 $A$ 任务，找到它在时间不超过 mid 的情况下最多还能完成多少个 $B$ 任务（即在预处理的 f[i][x][y][*] 中寻找任一不超过 mid 的 $y$），于是我们就能更新 g。如果最终 $g[P][A] \ge B$，说明给出的时间足够，否则就需要增大二分的上界。

这样就能在 $O(p \cdot n_A \cdot n_B)$ 的 DP 预处理和 $O(\log T \cdot p \cdot n_A^2)$ 的判定内求出最小完成时间。

#include <bits/stdc++.h>

using namespace std;

const int MAX_P = 20 + 5;
const int MAX_A = 60 + 5;
const int INF32 = 1e9;

int A, B, P;
int f[MAX_P][MAX_A][MAX_A][2];
int g[MAX_P][MAX_A];

int main() {
    scanf("%d%d%d", &A, &B, &P);
    for (int i = 1; i <= P; i ++) {
        int ta, tb, ka, kb;
        scanf("%d%d%d%d", &ta, &tb, &ka, &kb);
        for (int a = 0; a <= A; a ++) {
            for (int b = 0; b <= B; b ++) {
                if (a + b == 0) continue;
                f[i][a][b][0] = INF32;
                f[i][a][b][1] = INF32;
                for (int x = 1; x <= a; x ++) {
                    f[i][a][b][0] = min(f[i][a][b][0], f[i][a - x][b][1] + ta + ka * x * x);
                }
                for (int y = 1; y <= b; y ++) {
                    f[i][a][b][1] = min(f[i][a][b][1], f[i][a][b - y][0] + tb + kb * y * y);
                }
                // printf("f[%d][%d][%d]=%d,%d\n", i, a, b, f[i][a][b][0], f[i][a][b][1]);
            }
        }
        // printf("\n");
    }
    int l = 0, r = INF32;
    while (l < r) {
        int mid = l + r >> 1;
        for (int a = 0; a <= A; a ++) {
            g[0][a] = -INF32;
        }
        g[0][0] = 0;
        for (int i = 1; i <= P; i ++) {
            for (int a = 0, b; a <= A; a ++) {
                g[i][a] = g[i - 1][a];
            }
            for (int x = 0; x <= A; x ++) {
                int y = B;
                for (; y >= 0 && f[i][x][y][0] > mid && f[i][x][y][1] > mid; y --);
                // printf("i=%d,x=%d,y=%d\n", i, x, y);
                if (y >= 0) {
                    for (int a = 0; a <= A; a ++) {
                        g[i][a] = max(g[i][a], g[i - 1][a - x] + y);
                    }
                }
            }
            // for (int a = 0; a <= A; a ++) {
            //     printf("g[%d][%d]=%d\n", i, a, g[i][a]);
            // }
        }
        // printf("mid=%d g[P][A]=%d\n", mid, g[P][A]);
        if (g[P][A] >= B) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    printf("%d\n", l);
    return 0;
}