P3806. 最长连续手牌

题意

每张手牌有颜色（红/黄/蓝/绿）和数字（0~9）两个属性。第一张牌可以任意打出，之后每张牌必须与上一张打出的牌颜色相同或数字相同才能继续打出，直到手牌打完或无牌可接。求最优出牌顺序下最多能打出多少张牌。

思路

手牌数量很小，直接用回溯（DFS）穷举所有可能的出牌顺序即可。

参考代码把每张牌拆成 nums（数字）与 colors（颜色）两个平行数组，同一下标 i 对应同一张牌，用 used 数组标记牌是否已打出：

1. 递归状态：dfs(cur_color, cur_num, path_len, ...) 中前两个参数记录上一张打出的牌的颜色和数字，path_len 是当前出牌序列的长度。 2. 进入函数先更新答案：ans = max(path_len, ans) 放在函数开头，意味着任何中途状态都会被统计——不要求把手牌全部打完，打到「无牌可接」为止的最长序列同样会被记录，与题意吻合。 3. 横向枚举：遍历所有手牌，凡是未用过、且颜色或数字与上一张相同的牌都可作为下一张：标记 used[i] = True → 递归（path_len + 1）→ 回滚 used[i] = False，穷举所有可行的出牌顺序。 4. 枚举起点：主循环让每张牌轮流作为第一张（第一张不受任何限制），以 path_len = 1 进入递归，同样配对做标记与回滚。

这样所有可能的出牌序列都被覆盖，ans 即能打出的最多牌数。

复杂度

• 时间 O(N × N!)：N 为手牌数。递归树最坏枚举所有排列（N! 条路径），每层再扫一遍 N 张牌，通常记作 O(N!) 量级；因数据量小，实际运行可接受。
• 空间 O(N)：used 数组与递归栈深度。

坑点

• 更新答案必须放在递归入口处，而不是只在「手牌全部打完」时更新——否则会漏掉中途断掉的最长序列。
• 回溯的「标记 → 递归 → 回滚」三步缺一不可，主循环枚举起点时同样要配对做标记与回滚。