首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

HDU 2614 Beat:DFS 找最長遞增難度題目序列

     編輯:關於C++

問題描述

n 個問題(n<15),固定從問題 0 開始(耗時 0)。矩陣 T[i][j] 表示解完 i 後解 j 的耗時。要求後解問題的耗時 ≥ 前一題耗時。求最多能解多少題。

解題思路

狀態:(u, last_time, solved_mask)。但 n<15,直接 DFS 遍歷所有排列可行(最多 14! 太大),需剪枝。

觀察:耗時只依賴上一題,狀態可壓縮為 (u, last_time),用記憶化搜索或簡單 DFS + 剪枝(當前已解數 + 剩餘題數 ≤ 最優解則剪枝)。

代碼框架

int a[16][16], vis[16], n, maxn;
void dfs(int u, int cnt, int last_time) {
    maxn = max(maxn, cnt);
    if (maxn == n) return;
    for (int v = 1; v < n; ++v) if (!vis[v]) {
        int t = a[u][v];
        if (t >= last_time) {
            vis[v] = 1;
            dfs(v, cnt+1, t);
            vis[v] = 0;
        }
    }
}
int main() {
    while (scanf("%d", &n) == 1) {
        for (int i=0;i

關鍵點

  • 起點固定為 0,初始耗時 0。
  • 只能選擇未解過的題目,且耗時非遞減。
  • n ≤ 14,狀態空間極小,DFS 瞬間結束。
  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved