POJ 1040 Transportation：火車售票最大收益的 DFS + 剪枝

問題描述

火車從站 0 開往站 m，容量 n。有 p ≤ 22 個訂單，每單含 start, end, num。接受訂單則收益 (end-start)*num。車上任意時刻乘客數不能超過容量。求最大總收益。

解法：狀態空間搜索（DFS）

訂單數極小（≤22），可對每個訂單決策「接受/拒絕」。用 people[i] 記錄區間 [i-1, i] 上的乘客數。接受訂單前檢查沿途所有區段是否超載，超載則剪枝。按起點、終點排序訂單可提高剪枝效率。

關鍵代碼

struct Order { int s, e, p; } ord[30];
int cap, stations, orders;
int load[30]; // load[i] = 區段 i-1→i 的乘客數
int best;

void dfs(int idx, int money) {
    if (idx == orders) { best = max(best, money); return; }
    // 嘗試接受
    bool ok = true;
    for (int i = ord[idx].s + 1; i <= ord[idx].e; i++)
        if (load[i] + ord[idx].p > cap) { ok = false; break; }
    if (ok) {
        for (int i = ord[idx].s + 1; i <= ord[idx].e; i++) load[i] += ord[idx].p;
        dfs(idx+1, money + (ord[idx].e - ord[idx].s) * ord[idx].p);
        for (int i = ord[idx].s + 1; i <= ord[idx].e; i++) load[i] -= ord[idx].p;
    }
    // 拒絕
    dfs(idx+1, money);
}

int main() {
    while (scanf("%d%d%d",&cap,&stations,&orders), cap||stations||orders) {
        for (int i=0;i