专栏文章

题解：P2540 [NOIP2015 提高组] 斗地主 加强版

llihongru
P2540题解参与者 6已保存评论 11

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
11 条
当前快照
1 份
快照标识符
@miqeapwy
此快照首次捕获于
2025/12/04 03:23
3 个月前
此快照最后确认于
2025/12/04 03:23
3 个月前
查看原文

题目分析

这道题按照我们老师的话来说就是很神奇，写完才知道这道题有多么神奇。看到这道题依然只能想到搜索每一步出牌。
我们看题可以知道，牌的花色是不影响出牌的，所以输入时，我们不存每张牌长啥样，只存某种点数牌的数量，记作 ss。
当然，输入需要特别把 1(A)1(A) 记在 1515 的位置，这样才能更好的枚举顺子。以下分析均不带火箭，因为统计答案时直接使用更方便。
发现，有一部分出牌方法中，牌的点数和能否出是有关的，而另一部分中，牌的点数是无关的。我们依此大致可以把出牌分为两类。
  • 顺子类：单顺子/双顺子/三顺子
  • 其它类：炸弹/单张牌/对子牌/三张牌/三带一/三带二/四带二（需要拆解成四带二张和四带二对处理）
当然，不分类这道题依然可做，暴力卡时也能过。不过我更倾向于分类后使用这个“神奇”的剪枝来做。
牌的点数有关，我们没有什么好办法处理。但牌的点数无关就可以使用预处理的动态规划（四维：dp[单张数量][对子数量][三张数量][炸弹数量]）来减去搜索的时间复杂度。我们先来处理顺子类。

顺子类 - 搜索处理

我们使用暴力做法，暴力枚举顺子中每个点数的个数 aa，起点位置 ii 与可能的终点位置 jj。对于每一个起点位置，我们开一个计数器 cntcnt 记成功选中的牌的点数个数。
对于每一个可能的终点位置 jj，如果能够选择 aa 张牌，则选择 aa 张牌，并 cnt++;，如果不能，则直接跳出。
这里用数学直觉找出一个临界值用于判定，当顺子 cnt 足够时，aa 和 cntcnt 满足 cnt×a≥5cnt \times a \ge 5，对于本题 aa 的取值都是满足的。
由此可写出顺子部分的代码。注意删除和回溯。这份片段中，xx 代表走到这一步需要的步数。
CPP
for (int a = 1; a <= 3; a++){
	for (int i = 3; i <= 14; i++){
		int cnt = 0;
		for (int j = i; j <= 14; j++){
			if (s[j] >= a) cnt++;
			else break;
			if (a * cnt >= 5){
				for (int k = i; k <= j; k++){
					s[k] -= a;
				}
				dfs(x+1);
				for (int k = i; k <= j; k++){
					s[k] += a;
				}
			}
		}
		
	}
}

其它类 - 动态规划

我们记 aa 为单张数，bb 为对子数，cc 为三张数，dd 为炸弹数。记 dp[a][b][c][d] 表示这些牌需要用几次出完。具体如何转移见下表。
出牌种类aabbccdd附加值
单张牌a−1a-1bbccdd11
对子牌aab−1b-1ccdd11
三张牌aabbc−1c-1dd11
炸弹aabbccd−1d-111
三带一a−1a-1bbc−1c-1dd11
三带二aab−1b-1c−1c-1dd11
四带两张a−2a-2bbccdd11
四带两对aab−2b-2ccdd11
拆一对*a+2a+2b−1b-1ccdd00
拆三张*a+1a+1b+1b+1c−1c-1dd00
拆炸弹成两对*aab+2b+2ccd−1d-100
拆炸弹成单+三张*a+1a+1bbc+1c+1d−1d-100
注释：四带两张和四带两对都是四带二。所有带星号的都是拆牌操作，它们可能使得答案更优，且不需要消耗步数。
引入拆牌操作后，我们就需要仔细思考动态规划的顺序了。显然，d→c→b→ad \to c \to b \to a 的顺序是更合理的，保证了每个值被推算前，它需要用到的值都已经推算完成。
预处理时进行动态规划即可。为了减少代码量，可以使用临时变量。注意边界问题，初始值的设置与 00 值不能够被覆盖。
CPP
for (int d = 0; d <= 5; d++){
	for (int c = 0; c <= 8; c++){
		for (int b = 0; b <= 12; b++){
			for (int a = 0; a <= 23; a++){
				if (!a && !b && !c && !d) continue;
				int s = 0x3f3f3f3f;
				
				if (a) s = min(s, dp[a-1][b][c][d] + 1);
				if (b) s = min(s, dp[a][b-1][c][d] + 1);
				if (c) s = min(s, dp[a][b][c-1][d] + 1);
				if (d) s = min(s, dp[a][b][c][d-1] + 1);
				
				if (a && c) s = min(s, dp[a-1][b][c-1][d] + 1);
				if (b && c) s = min(s, dp[a][b-1][c-1][d] + 1);
				if (a >= 2 && d) s = min(s, dp[a-2][b][c][d-1] + 1);
				if (b >= 2 && d) s = min(s, dp[a][b-2][c][d-1] + 1);
				
				if (b) s = min(s, dp[a+2][b-1][c][d]);
				if (c) s = min(s, dp[a+1][b+1][c-1][d]);
				if (d) s = min(s, dp[a][b+2][c][d-1]);
				if (d) s = min(s, dp[a+1][b][c+1][d-1]);
					
				dp[a][b][c][d] = s;
			}
		}
	}
}

剪枝的具体实现

由于牌一共就 1414 种（不加大小王），我们直接暴力统计即可。调用时注意，双王可作单张，也可作火箭（即多加一步）。
CPP
memset(c, 0, sizeof c);
for (int i = 2; i <= 14; i++) c[s[i]]++;
ans = min(ans, x + dp[c[1]+s[0]][c[2]][c[3]][c[4]]);
if (s[0] == 2) ans = min(ans, x + dp[c[1]][c[2]][c[3]][c[4]] + 1);
当然，不要忘记我们的最简单的剪枝“最优性剪枝”。
CPP
if (x >= ans) return ;
最终将上面的代码块串在一起，加上输入输出就是本题的代码。

题目总结与参考代码

本题的“神奇之处”就在于使用动态规划进行剪枝。最后提醒一句，本题多测，不要忘记清空和重置答案。
CPP
#include <bits/stdc++.h>
using namespace std;

int T, n, s[25], c[5], dp[26][15][10][6], ans;

void dfs(int x){
	if (x >= ans) return ;
	
	memset(c, 0, sizeof c);
	for (int i = 2; i <= 14; i++) c[s[i]]++;
	ans = min(ans, x + dp[c[1]+s[0]][c[2]][c[3]][c[4]]);
	if (s[0] == 2) ans = min(ans, x + dp[c[1]][c[2]][c[3]][c[4]] + 1);
	
	for (int a = 1; a <= 3; a++){
		for (int i = 3; i <= 14; i++){
			int cnt = 0;
			for (int j = i; j <= 14; j++){
				if (s[j] >= a) cnt++;
				else break;
				if (a * cnt >= 5){
					for (int k = i; k <= j; k++){
						s[k] -= a;
					}
					dfs(x+1);
					for (int k = i; k <= j; k++){
						s[k] += a;
					}
				}
			}
			
		}
	}
	return ;
}

int main(){
	for (int d = 0; d <= 5; d++){
		for (int c = 0; c <= 8; c++){
			for (int b = 0; b <= 12; b++){
				for (int a = 0; a <= 23; a++){
					if (!a && !b && !c && !d) continue;
					int s = 0x3f3f3f3f;
					
					if (a) s = min(s, dp[a-1][b][c][d] + 1);
					if (b) s = min(s, dp[a][b-1][c][d] + 1);
					if (c) s = min(s, dp[a][b][c-1][d] + 1);
					if (d) s = min(s, dp[a][b][c][d-1] + 1);
					
					if (a && c) s = min(s, dp[a-1][b][c-1][d] + 1);
					if (b && c) s = min(s, dp[a][b-1][c-1][d] + 1);
					if (a >= 2 && d) s = min(s, dp[a-2][b][c][d-1] + 1);
					if (b >= 2 && d) s = min(s, dp[a][b-2][c][d-1] + 1);
					
					if (b) s = min(s, dp[a+2][b-1][c][d]);
					if (c) s = min(s, dp[a+1][b+1][c-1][d]);
					if (d) s = min(s, dp[a][b+2][c][d-1]);
					if (d) s = min(s, dp[a+1][b][c+1][d-1]);
					
					dp[a][b][c][d] = s;
				}
			}
		}
	}
	cin >> T >> n;
	while (T--){
		memset(s, 0, sizeof s);
		for (int i = 1; i <= n; i++){
			int x, y; cin >> x >> y;
			if (x == 1) x = 14;
			s[x]++;
		}
		ans = 0x7f7f7f7f;
		dfs(0);
		cout << ans << endl;
	}
	return 0;
}

评论

共 11 条评论，欢迎与作者交流。

正在加载评论...