HDU 2614 Beat：DFS 搜索最長合法任務序列

問題描述

有 N 個任務（N ≤ 16），任務 i 到任務 j 需時間 time[i][j]。從任務 0 開始，每個任務最多做一次，且下一任務的開始時間 ≥ 上一任務的結束時間（即 time[cur][next] ≥ 當前時間）。求最多能完成多少個任務。

解法：狀態壓縮 DFS + 剪枝

• N ≤ 16 → 可用 used[16] 陣列或位掩碼標記已做任務。
• 從任務 0 開始（used[0]=1），當前時間 t=0，已完成數 cnt=1。
• DFS 枚舉下一任務 i：!used[i] && time[cur][i] >= t。
• 遞歸進入：used[i]=1; dfs(i, time[cur][i], cnt+1); used[i]=0;。
• 全局維護 most = max(most, cnt)。
• 剪枝：若 cnt + (n - 已用數) ≤ most 可提前返回（代碼未顯式實現，但 N=16 暴力 DFS 可過）。

關鍵代碼

#include 
#include 
#include 
using namespace std;

#define MAXSIZE 16
int n, most;
int time[MAXSIZE][MAXSIZE];
int used[MAXSIZE];

void dfs(int cur, int t, int cnt) {
    most = max(most, cnt);
    if (cnt == n) return;
    for (int i = 1; i < n; ++i) {
        if (!used[i] && time[cur][i] >= t) {
            used[i] = 1;
            dfs(i, time[cur][i], cnt + 1);
            used[i] = 0;
        }
    }
}

int main() {
    while (scanf("%d", &n) != EOF) {
        most = 0;
        memset(used, 0, sizeof(used));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                scanf("%d", &time[i][j]);
        used[0] = 1;
        dfs(0, 0, 1);
        printf("%d\n", most);
    }
    return 0;
}

複雜度分析

• 狀態數上界：所有排列 ∑ P(n,k) ≈ n! × e，N=16 時 ~2e13 太大。
• 但時間約束 time[cur][i] >= t 極強剪枝，實際搜索樹極小。
• 加上 used 標記避免重複，單測試案例毫秒級通過（原文 31MS）。

優化方向

1. 記憶化搜索 (DP)：狀態 (cur, t, mask)，但 t 取值範圍大，難直接 DP。
2. 按時間排序：預處理每個任務的可轉移列表按 time 升序，DFS 時可二分/早停。
3. 位掩碼 + 迭代加深：用 int mask 替換 used[]，配合 __builtin_popcount 剪枝。

總結

HDU 2614 是小規模圖搜索典型題：N≤16 暗示狀態壓縮/DFS，時間單調約束提供強剪枝，used[] 回溯正確性關鍵。代碼簡潔，邏輯清晰，是 DFS 回溯入門好例。若 N 擴大至 20+，需引入 DP/啟發式搜索。