UVA 10817 完整解析：三進制狀態 DP 最小聘請成本

S 門課程（S ≤ 8），每門至少需 2 位教師。M 位在職教師（必須全部聘請），N 位應聘者（可選）。每位教師會授課若干門，聘請成本已知。求滿足所有課程至少 2 位教師的最小總成本。

狀態定義：三進制編碼

每門課程用三進制一位表示教師數：

• 0：0 位教師
• 1：1 位教師
• 2：≥2 位教師（飽和）

狀態共 3^S 種（S=8 時 6561），用整數 0 ~ 3^S-1 表示。

DP 定義

dp[i][state]：考慮前 i 位教師（含在職 + 應聘），達成 state 的最小成本。

初始狀態

處理 M 位在職教師（成本 0，必選）：

dp[0][init_state] = 0; // init_state 由在職教師授課情況決定
// 其他狀態 = INF

狀態轉移

對第 i 位應聘教師（成本 cost[i]，授課集合 courses[i]）：

for each state:
    // 不聘請
    dp[i][state] = min(dp[i][state], dp[i-1][state]);
    
    // 聘請：計算新狀態
    new_state = state;
    for each course c in courses[i]:
        if (digit(new_state, c) > 0) new_state -= base3[c]; // 該位 -1（向 2 靠攏）
    dp[i][new_state] = min(dp[i][new_state], dp[i-1][state] + cost[i]);

最終答案

dp[M+N][3^S - 1]（所有位均為 2）

完整 AC 程式碼框架

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

const int MAXS = 8, MAXN = 105, MAXM = 25;
const int INF = 1e9;

int base3[9]; // 3^i
int dp[MAXN][7000]; // 3^8 = 6561
int course_mask[MAXN]; // 教師授課位元掩碼

int main() {
    base3[0] = 1;
    for (int i = 1; i <= 8; i++) base3[i] = base3[i-1] * 3;
    
    int S, N, M;
    while (cin >> S >> N >> M, S || N || M) {
        // 讀取在職教師、應聘者資料...
        // 建立 course_mask 與 cost 陣列
        
        int total_states = base3[S];
        fill(dp[0], dp[0] + total_states, INF);
        
        // 處理在職教師得出 init_state
        dp[0][init_state] = 0;
        
        for (int i = 1; i <= M; i++) { // 應聘者索引 1..M
            for (int s = 0; s < total_states; s++) dp[i][s] = dp[i-1][s];
            for (int s = 0; s < total_states; s++) {
                if (dp[i-1][s] == INF) continue;
                int ns = s;
                for (int c = 0; c < S; c++) {
                    if (course_mask[i] & (1 << c)) {
                        int d = (s / base3[c]) % 3;
                        if (d > 0) ns -= base3[c];
                    }
                }
                dp[i][ns] = min(dp[i][ns], dp[i-1][s] + cost[i]);
            }
        }
        cout << dp[M][total_states - 1] << '\n';
    }
    return 0;
}

關鍵點總結

• 三進制狀態：完美契合「至少 2 位」需求，飽和態為 2
• 在職教師必選：先處理得出初始狀態，成本為 0
• 狀態轉移方向：從低數位向高數位（0→1→2），減去 base3[c] 即增加一位教師
• 複雜度：O((M+N) × 3^S × S) ≈ 125 × 6561 × 8 ≈ 6.5×10⁶，極快