HDU 3433 A Task Process：DP + 二分求最短完成時間

問題描述

N 人，每人完成一個 A 任務耗時 a[i]，一個 B 任務耗時 b[i]。需完成 X 個 A 任務和 Y 個 B 任務，每人可分配任意數量任務，但總耗時不超過 T。求最小 T。

DP 判斷給定 T 是否可行

dp[i][j] = 前 i 人完成 j 個 A 任務後，最多能完成多少 B 任務。
轉移：dp[i][j] = max(dp[i][j], dp[i-1][j-k] + (T - k*a[i])/b[i])，枚舉第 i 人做 k 個 A 任務。
初始 dp[1][j] = (T - j*a[1])/b[1]。
若 dp[N][X] >= Y 則 T 可行。

二分搜索最小 T

單調性：T 越大，可完成任務越多。上界可設為 min_i(a[i]*X + b[i]*Y)。二分區間 [1, upper]。

代碼框架

bool check(int T) {
    memset(dp, -1, sizeof(dp));
    for (int j=0; j*a[1]<=T && j<=X; ++j) dp[1][j] = (T - j*a[1])/b[1];
    for (int i=2; i<=N; ++i)
        for (int j=0; j<=X; ++j)
            for (int k=0; k<=j && k*a[i]<=T; ++k)
                if (dp[i-1][j-k]!=-1)
                    dp[i][j] = max(dp[i][j], dp[i-1][j-k] + (T - k*a[i])/b[i]);
    return dp[N][X] >= Y;
}

int main() {
    int T; scanf("%d", &T);
    for (int cs=1; cs<=T; ++cs) {
        scanf("%d%d%d", &N, &X, &Y);
        int upper = INF;
        for (int i=1; i<=N; ++i) {
            scanf("%d%d", &a[i], &b[i]);
            upper = min(upper, a[i]*X + b[i]*Y);
        }
        int L=1, R=upper, ans=upper;
        while (L <= R) {
            int mid = (L+R)/2;
            if (check(mid)) { ans = mid; R = mid-1; }
            else L = mid+1;
        }
        printf("Case %d: %d\n", cs, ans);
    }
}

複雜度

DP O(N·X²)，X≤200，N≤200 → 8×10⁶/次。二分 ~log(10⁷)≈24 次。總 ~2×10⁸ 操作，C++ 可通過。可優化：單調隊列/凸包優化 DP 到 O(N·X)。