HDU 2079 選課時間：母函數動態規劃解法詳解

HDU 2079 選課時間：母函數動態規劃解法詳解

題目大意

給定 k 種課程，第 i 種學分為 a[i]、有 b[i] 門（視為無差別）。求湊出總學分 n 的組合數。n ≤ 40, k ≤ 8, a ≤ 8, b ≤ 10。

母函數 / DP 思路

每種課程的生成函數為 (1 + x^a + x^{2a} + ... + x^{b*a})。將所有生成函數相乘，x^n 的係數即為答案。用兩個陣列 s[]（當前係數）與 c[]（暫存）滾動計算。

核心程式碼（C）

#include <stdio.h>
#include <string.h>

int c[45], s[45];
int a[8], b[8];

int main() {
    int T, n, k;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &k);
        for (int i = 0; i < k; ++i) scanf("%d %d", &a[i], &b[i]);

        memset(s, 0, sizeof(s));
        for (int i = 0; i <= n && i <= a[0] * b[0]; i += a[0]) s[i] = 1; // 初始化第 0 種

        for (int i = 1; i < k; ++i) {
            memset(c, 0, sizeof(c));
            for (int j = 0; j <= n; ++j) {
                for (int t = 0; t + j <= n && t <= a[i] * b[i]; t += a[i]) {
                    c[j + t] += s[j];
                }
            }
            for (int j = 0; j <= n; ++j) {
                s[j] = c[j];
                c[j] = 0;
            }
        }
        printf("%d\n", s[n]);
    }
    return 0;
}

複雜度

• 時間：O(k * n * max(b[i]))，極小範圍內極快。
• 空間：O(n)。

關鍵點

• 母函數與 01/完全背包 DP 本質相同，此處為「有限件數」的多重背包變體。
• 陣列大小 45 足夠覆蓋 n ≤ 40。
• 輸入可能有多組測資，記得迴圈處理。