P2540 [NOIP2015 提高组] 斗地主 加强版
tangtangpeng
·
·
个人记录
思路
优雅，太优雅了！
首先声明，这个思路源自某位大佬。
考虑把所有牌分成两类，不定长的连牌（如顺子、连对、飞机）和其他定长的（如单排、对子、三带一、炸弹等等）。
第一种可以通过暴搜枚举，后一种用 dp 神操作转移。
那么根据单张、对子、三张、炸弹、三带一、三带二、四带二的出牌规则就可以写出 $dp$ 转移了。
但有一种特殊情况，就是三张可以拆分为单排和对子，炸弹可以拆分为单排和三张，那么就有：
\begin{array}{l}
f[i + 1][j + 1][k - 1][z][l] \to f[i][j][k][z]][l]\
f[i + 1][j][k + 1][z - 1][l] \to f[i][j][k][z]][l]
\end{array}
为什么炸弹不拆解为两个对子、三张不拆解为三个单张呢？
我们拆牌的意义是什么？就是可以凑齐比如三带一、四带二里面的边角余料，出此之外出整牌一定是不劣的。
预处理出这些后，我们 $dfs$ 时暴力枚举所有顺子、连对和飞机，然后加上已经预处理出的剩下的牌的最小出牌次数取 $\min$ 就是答案了。
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
int T, n, a[N];
int f[N][N][N][N][3];
int ans;
int cnt[10];
void dfs(int x)
{
int tot;
bool flag;
if(x >= ans) return;
for(int k = 1; k <= 3; k++)
for(int i = 1; i <= 12; i++)
{
flag = 1;
if(k == 1) tot = 5;
if(k == 2) tot = 3;
if(k == 3) tot = 2;
while(flag && i + tot - 1 <= 12)
{
for(int j = 1; j <= tot; j++)
if(a[i + j - 1] < k)
{
flag = 0;
break;
}
if(flag == 0) continue;
for(int j = 1; j <= tot; j++)
a[i + j - 1] -= k;
dfs(x + 1);
for(int j = 1; j <= tot; j++)
a[i + j - 1] += k;
tot++;
}
}
for(int i = 1; i <= 5; i++) cnt[i] = 0;
for(int i = 1; i <= 13; i++) cnt[a[i]]++;
cnt[5] = a[14];
ans = min(ans, x + f[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]]);
}
void init()
{
int x = 100;
memset(f, 0x3f, sizeof(f));
f[0][0][0][0][0] = 0;
for(int z = 0; z <= n; z++)
for(int k = 0; k <= n; k++)
for(int i = 0; i <= n; i++)
for(int j = 0; j <= n; j++)
for(int l = 0; l <= n; l++)
{
x = 100;
if(i > 0) x = min(x, f[i - 1][j][k][z][l] + 1);
if(j > 0) x = min(x, f[i][j - 1][k][z][l] + 1);
if(k > 0) x = min(x, f[i][j][k - 1][z][l] + 1);
if(z > 0) x = min(x, f[i][j][k][z - 1][l] + 1);
if(l > 0) x = min(x, f[i][j][k][z][l - 1] + 1);
if(l > 1) x = min(x, f[i][j][k][z][l - 2] + 1);
//单张、对子、三张、炸弹、单张王、王炸
if(i > 0 && k > 0) x = min(x, f[i - 1][j][k - 1][z][l] + 1);
if(k > 0 && l > 0) x = min(x, f[i][j][k - 1][z][l - 1] + 1);
//三带一
if(j > 0 && k > 0) x = min(x, f[i][j - 1][k - 1][z][l] + 1);
//三带二
if(i > 1 && z > 0) x = min(x, f[i - 2][j][k][z - 1][l] + 1);
if(i > 0 && z > 0 && l > 0) x = min(x, f[i - 1][j][k][z - 1][l - 1] + 1);
if(z > 0 && l > 1) x = min(x, f[i][j][k][z - 1][l - 2] + 1);
if(j > 0 && z > 0) x = min(x, f[i][j - 1][k][z - 1][l] + 1);
if(j > 1 && z > 0) x = min(x, f[i][j - 2][k][z - 1][l] + 1);
if(z > 1) x = min(x, f[i][j][k][z - 2][l] + 1);
//四带二
if(z > 0) x = min(x, f[i + 1][j][k + 1][z - 1][l]);
if(k > 0) x = min(x, f[i + 1][j + 1][k - 1][z][l]);
//拆单
f[i][j][k][z][l] = min(f[i][j][k][z][l], x);
}
}
void work()
{
memset(a, 0, sizeof(a));
ans = n;
for(int i = 1; i <= n; i++)
{
int num, col;
scanf("%d%d", &num, &col);
if(num == 0)
{
a[14]++;
continue;
}
if(num >= 3) a[num - 2]++;
if(num == 1) a[12]++;
if(num == 2) a[13]++;
}
dfs(0);
printf("%d\n", ans);
}
int main()
{
scanf("%d%d", &T, &n);
init();
while(T--) work();
}
```