题面
小明被劫持到X赌城，被迫与其他3人玩牌。
一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。
这时，小明脑子里突然冒出一个问题：
如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序，自己手里能拿到的初始牌型组合一共有多少种呢？
题解
枚举，动态规划，DFS
- DFS
枚举13种不同点数的牌每种取多少张(0-4张)，最后刚好达到13张牌的方案数。
注意一定要剪枝，当某个状态的获取的牌的数量超过13张，立即剪枝。
- DP
状态表示：记 f[i][j] 表示前 i 种牌总共拿到 j 张的方案数。
初始状态：
状态转移方程：
答案：
3598180
代码
- DFS
#include<bits/stdc++.h>
using namespace std;
int ans = 0;
void dfs(int u, int s) {
if (u == 13) return; //
for (int i = 0; i <= 4; i++) { //枚举点数为 u + 1 的牌取 i 张的状态
if (s + i > 13) break; //剪枝
if (s + i < 13) dfs(u + 1, s + i);
else ans++;
}
}
int main() {
dfs(0, 0);
cout << ans << endl;
return 0;
}
- DP
#include<bits/stdc++.h>
using namespace std;
int f[15][15];
int n = 13;
int main() {
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= 4; k++) {
if (j >= k) f[i][j] += f[i - 1][j - k];
}
}
}
cout << f[n][n] << endl;
return 0;
}
| 标题： | 2015年第六届蓝桥杯省赛-G. 牌型种树 |
|---|---|
| 链接： | https://www.fightingok.cn/detail/176 |
| 更新： | 2022-09-18 22:45:35 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |