题解

把问题理解成“给定一个截止时间 $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;
}