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