HDOJ 2614 Beat：DFS 搜索最大問題解決序列

問題描述

有 n < 15 個問題，編號 0~n-1。先解問題 0（耗時 0）。解完問題 i 後，解問題 j 需耗時 T[i][j]。要求每次選擇的問題耗時 ≥ 上一題耗時。求最多能解多少題。

核心思路：DFS + 剪枝

• 狀態：(當前問題, 當前已解數, 上一題耗時)。
• 從問題 0 開始，遞歸嘗試所有合法下一題（T[cur][next] ≥ last_time 且未解過）。
• 記錄最大解題數。
• n ≤ 14，狀態空間極小，無需記憶化，直接 DFS 回溯即可。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 15;
int T[MAXN][MAXN];
bool vis[MAXN];
int n, ans;

void dfs(int cur, int cnt, int last_time) {
    ans = max(ans, cnt);
    if (cnt == n) return;
    for (int nxt = 0; nxt < n; ++nxt) {
        if (vis[nxt]) continue;
        int cost = T[cur][nxt];
        if (cost >= last_time) {
            vis[nxt] = true;
            dfs(nxt, cnt + 1, cost);
            vis[nxt] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n) {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                cin >> T[i][j];
        fill(vis, vis+n, false);
        ans = 0;
        vis[0] = true;
        dfs(0, 1, 0);
        cout << ans << '\n';
    }
    return 0;
}

複雜度

最多 n! 排列，但 n ≤ 14 且耗時單調約束大幅剪枝，實際極快。

關鍵點

1. 第一題固定為 0，耗時 0。
2. 耗時非遞減：cost >= last_time。
3. 訪問標記 vis 防止重複解題。