题解

题目类型：搜索 / 记忆化搜索 / 手牌出完最小步数
核心算法：深度优先搜索（DFS）+ 剪枝 + 状态哈希记忆化

一、题意概述

本题是一个类似 “斗地主最少出牌次数” 的问题。
给定若干张牌（每张牌的点数和张数），我们要求在遵循出牌规则的前提下，最少几次出完手牌。

出牌规则（从代码分析得出）包含：

• 单牌、对子、三张、炸弹（四张）；
• 顺子（≥5 连续单牌）；
• 连对（≥3 连续对子）；
• 飞机（≥2 连续三张）；
• 三带一 / 三带二、四带二（单/双） 等复合组合。

目标是求出：将给定牌型全部出完所需的最小次数。

二、核心思路

整体采用 深度优先搜索（DFS）+ 记忆化剪枝。

1. 状态表示

• 用数组 PAP[17] 表示每种牌点（3~16，对应 3~A, 2, 小王, 大王）的剩余张数。
• dep 表示当前搜索的目标层数（尝试在 dep 步内出完）。
• find(PAP, x) 函数将当前状态哈希成一个整数索引，用于在全局数组 T[] 中做记忆化，防止重复搜索。

2. 搜索流程

dfs(PAP, x, last)：

• x：当前已经出的次数；
• last：上一轮出的最大牌型长度（用于剪枝优化）。

搜索流程：

1. 剪枝 1：重复状态
   若当前状态哈希值已在 T[] 中标记，则直接返回。
2. 剪枝 2：层数越界
   若当前步数 x > dep，停止并标记此状态。
3. 结束条件
   若所有牌出完（通过统计判断 t == dep），则置 p = true 表示找到答案。
4. 生成所有可行出牌组合
   通过三重循环，枚举所有可能的出牌类型：
   • 顺子、连对、飞机；
   • 三带一、三带二；
   • 四带两单、四带两对；
   • 纯单、纯对、纯三。 每次出牌后递归进入下一层 dfs。
5. 恢复状态（回溯）
   在每次递归后恢复 PAP[]，保持全局一致。

三、剪枝策略

1. 记忆化标记
   数组 T[10000010] 用哈希存储访问状态，防止同状态重复搜索。
2. 启发式深度限制
   主函数中逐层增加 dep，即“迭代加深搜索”思想，保证找到最小步数后立即停止。
3. 冗余状态提前剪枝
   若计算得出当前出完需要的最少步数大于 dep，直接返回。

四、主函数流程

for (dep = 0; true; dep++) {
    memset(T, false, sizeof(T));
    dfs(PAP, 0, 114514);
    if (p) {
        cout << dep << endl;
        break;
    }
}

• 从 dep = 0 开始逐层尝试；
• 一旦 p == true（代表能在 dep 步内出完），即输出结果并退出；
• 类似 IDDFS（迭代加深深搜）的做法，确保找到最优解。

五、复杂度分析

• 状态空间极大，但依靠哈希剪枝与深度限制，大量重复状态被避免；
• 平均复杂度远低于指数级；
• 空间复杂度主要取决于 T[] 的状态存储，约 ( O(10^7) )。

六、关键函数说明

find(PAP, x)

对当前手牌状态进行哈希映射，用于记忆化。
通过多项式取模生成唯一值：

for (int i = 3; i <= 16; i++)
    ans = (ans * 3 + PAP[i]) % 10000000;

dfs(PAP, x, last)

递归枚举所有可出牌型，更新最优步数。

七、总结

• 本题是 斗地主最少出牌次数 的高难度搜索题。
• 核心技术点：
  • 状态压缩哈希；
  • 记忆化 DFS；
  • 剪枝与迭代加深。
• 结构紧凑、逻辑复杂但思路清晰：
  搜索 + 剪枝 + 记忆化 = 最小出牌次数。

#include<bits/stdc++.h>
using namespace std;
bool p, T[10000010];
int dep;
int find(int PAP[], int x)
{
	int ans = x;
	for (int i = 3;i <= 16;i++)
	{
		ans = (ans * 3 + PAP[i]) % 10000000;
	}
	return ans;
}
void dfs(int PAP[], int x, int last)
{
	if (p)
	{
		return;
	}
	for (int i = 0;i <= x;i++)
	{
	    if (T[find(PAP, i)])
        {
        	return;
        }
	}
	if (x > dep)
	{
		T[find(PAP, x)] = true;
		return;
	}
	int t = x, summ = 0, maxn = 0, idx = 0, X[1000][17] = {};
	for (int i = 3;i <= 16;i++)
	{
		t += (PAP[i] + 3) / 4;
		summ += PAP[i];
		maxn = max(maxn, PAP[i]);
	}
	if (t == dep)
	{
	    p = true;
	    return;
	}
	if (x + (summ - 1) / last + 1 > dep)
	{
		T[find(PAP, x)] = true;
		return;
	}
	int sum = 0;
	for (int i = 3;i <= 14;i++)
	{
		if (PAP[i] == 0)
		{
			sum = 0;
			continue;
		}
		else
		{
		    sum++;
		}
		if (sum >= 5)
		{
			idx++;
			for (int j = i - sum + 1;j <= i;j++)
			{
				PAP[j]--;
				X[idx][j]++;
			}
			maxn = max(maxn, sum);
			for (int j = i - sum + 1;j <= i;j++)
			{
				PAP[j]++;
			}
		}
	}
	sum = 0;
	for (int i = 3;i <= 14;i++)
	{
		if (PAP[i] <= 1)
		{
			sum = 0;
			continue;
		}
		else
		{
		    sum++;
		}
		if (sum >= 3)
		{
			idx++;
			for (int j = i - sum + 1;j <= i;j++)
			{
				PAP[j] -= 2;
				X[idx][j] += 2;
			}
			maxn = max(maxn, sum * 2);
			for (int j = i - sum + 1;j <= i;j++)
			{
				PAP[j] += 2;
			}
		}
	}
	sum = 0;
	for (int i = 3;i <= 14;i++)
	{
		if (PAP[i] <= 2)
		{
			sum = 0;
			continue;
		}
		else
		{
		    sum++;
		}
		if (sum >= 2)
		{
			idx++;
			for (int j = i - sum + 1;j <= i;j++)
			{
				PAP[j] -= 3;
				X[idx][j] += 3;
			}
			maxn = max(maxn, sum * 3);
			for (int j = i - sum + 1;j <= i;j++)
			{
				PAP[j] += 3;
			}
		}
	}
	for (int i = 3;i <= 15;i++)
	{
		if (PAP[i] < 4)
		{
			continue;
		}
		PAP[i] -= 4;
		for (int j = 3;j <= 15;j++)
		{
			if (PAP[j] <= 1)
			{
				continue;
			}
			PAP[j] -= 2;
			for (int k = 3;k <= 15;k++)
			{
				if (PAP[k] > 1)
				{
					PAP[k] -= 2;
					idx++;
					X[idx][i] += 4;
					X[idx][j] += 2;
					X[idx][k] += 2;
					maxn = max(maxn, 8);
					PAP[k] += 2;
				}
			}
			PAP[j] += 2;
		}
		for (int j = 3;j <= 16;j++)
		{
			if (PAP[j] == 0)
			{
				continue;
			}
			PAP[j]--;
			for (int k = 3;k <= 16;k++)
			{
				if (PAP[k])
				{
					PAP[k]--;
					idx++;
					X[idx][i] += 4;
					X[idx][j]++;
					X[idx][k]++;
					maxn = max(maxn, 6);
					PAP[k]++;
				}
			}
			PAP[j]++;
		}
		PAP[i] += 4;
	}
	for (int i = 3;i <= 15;i++)
	{
		if (PAP[i] < 3)
		{
			continue;
		}
		PAP[i] -= 3;
		for (int j = 3;j <= 16;j++)
		{
			if ((PAP[j] >= 2) && (j != 16))
			{
				PAP[j] -= 2;
				idx++;
				X[idx][i] += 3;
				X[idx][j] += 2;
				maxn = max(maxn, 5);
				PAP[j] += 2;
			}
			if (PAP[j] >= 1)
			{
				PAP[j]--;
				idx++;
				X[idx][i] += 3;
				X[idx][j]++;
				maxn = max(maxn, 4);
				PAP[j]++;
			}
		}
		PAP[i] += 3;
	}
	for (int i = 1;i <= idx;i++)
	{
		for (int j = 3;j <= 16;j++)
		{
			PAP[j] -= X[i][j];
		}
		dfs(PAP, x + 1, maxn);
		for (int j = 3;j <= 16;j++)
		{
			PAP[j] += X[i][j];
		}
	}
	if (!p)
	{
		T[find(PAP, x)] = true;
	}
}
int main()
{
	//freopen("in.txt", "r", stdin);
	int t, n;
	cin >> t >> n;
	while (t--)
	{
		p = false;
		int PAP[17] = {};
		for (int i = 0;i < n;i++)
		{
			int u, v;
			cin >> u >> v;
			if (u == 0)
			{
				u = 16;
			}
			if ((u == 1) || (u == 2))
			{
				u += 13;
			}
			PAP[u]++;
		}
		for (dep = 0;true;dep++)
		{
			memset(T, false, sizeof(T));
			dfs(PAP, 0, 114514);
			if (p)
			{
				cout << dep << endl;
				break;
			}
		}
	}
}