题解 P2540 【斗地主增强版】
暴力出奇迹，我是搜索小名士。
博客中观看体验更佳：My Blog
分析
其实我一开始没有想着去写100分的代码，因为爆搜的复杂度太大，然后这题好像我只会爆搜。
第一步
首先，很容易想到一种最纯粹的爆搜。每层都将当前剩余牌可行的情况全部枚举判断，然后打出一种可行的牌进入下一层继续搜索。
搜索是盲目的，我们考虑剪枝。 ——某金牌教练一个剪枝是搜索必备，如果当前答案大于或等于已知的最小答案，我们接下来的搜索一定不会更新答案，所以回到上一层。
然后再继续想，可以加一个启发式剪枝，计算打出所有剩余牌的最大出牌次数。
用肉眼就能推出，一副牌的最大出牌次数就是牌的数码种类数，两个王在此可以算一种。然后我们计算出当前最大出牌次数加上当前已出牌次数去更新答案，这样就会剪去接下来的一些较差的出牌方法。
第二步
上面的方法必不能通过本题，不需要尝试也能猜测。所以还要继续剪枝。
再稍微思考一下，我们每层搜索将全部出牌方法都枚举一遍过于暴力。我们发现，有些出牌方法自始至终永远不可行，并且可行的出牌方法一定越来越少。然后就想到了预处理，我们预处理出最开始的手牌的可行出牌方法。
这里我的代码极其鬼畜，可能对代码能力有些要求。我用了一些自认为省空间，用起来舒服的方法。将可行方法的信息写成结构体，就不演示，代码中在讲讲。
最关键的是，我们要计算每种方法的出牌数量，可用来后续我们继续优化。
这些代码全部可在输入后搜索前执行，我是将这些可行方法放到了vector中。在搜索时，枚举vector的所有元素。再进行一次针对性判断，也就是判断需要打的那几张牌就够了。
第三步
我们说记录了每种方法的出牌数量。那我们从大到小排序，这样大概能优化时间，我也不知道。
在这我们提个醒，如果你将王炸、对子、三张牌放入可行方法中，那你一定会TLE，因为我一开始就是这样。（实践出真知，但其实非加强版不需要，到这里已经通过了）
我们每层搜索，只枚举上一层搜索枚举没有枚举到的就行了，这是个小剪枝。如果当前方法的出牌数大于当前剩余数量，就直接枚举下一个出牌方法，这也可算上个小剪枝。然后还要再次判断当前剩余的牌下这种方法是否可行。
还有几个小的要点，我们不管是预处理，还是每层搜索都要用到一个小动态规划，用来求某个牌当左端点，可以连成（单、双、三）顺子的最大长度。鉴于这个题的难度，我相信大家都会这个小动归。
然后还有几个提示，四带二可以带两个相同数码的对子（俗称炸弹），同理，可以带两个相同数码的一张牌（俗称对子）。然后1当14，大小王当15、16比较好写代码。
经过多次提交更改调试，终于通过了本题。
代码
不开O2两秒多通过。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int T, n;
struct PAI {
int num, col;
} ps[30];
// 记录牌的数码，颜色（没啥用）
#define SHUNZI 3
#define SANDAI 4
#define SIDAI 5
//顺子、三带、四带
struct CP {
// 记录出牌方法的信息
int typ, l, r, k1, k2, siz;
// typ 为宏定义的值
// siz 为出牌数量
// l r 多种使用。l：顺子左端点，其他为最多的那张牌。r：顺子右端点，其他为少的那张牌需要的个数
// k1 k2 三带、四带使用，表示附带哪一（两）张牌。
CP(int typ, int siz, int l= 0, int r= 0, int k1= 0, int k2= 0) {
this->typ= typ, this->siz= siz, this->l= l, this->r= r, this->k1= k1, this->k2= k2;
}
inline int operator<(const CP &c2) const {
return siz > c2.siz;
}
};
int pai[20], bestans, us3[20], us2[20], us1[20];
vector< CP > v;
void dfs(int nown, int nowa, int ls) {
if(nowa >= bestans) return;
// 小剪枝
bestans= min(bestans, nowa + nown);
// 更新答案，全部单打（没什么用）
if(!nown) return;
int res= 0, us[4][20];
memset(us, 0, sizeof(us));
for(int i= 2; i <= 16; i++) res+= (pai[i] != 0);
if(pai[15] && pai[16]) --res;
// 15、16为大小王，主程序中有，大小王可以王炸
bestans= min(bestans, nowa + res);
// 再次更新答案（剪枝）
for(int i= 14, cnt= 0; i >= 2; i--) {
if(pai[i] < 1) continue;
us[1][i]= us[1][i + 1] + 1;
if(pai[i] < 2) continue;
us[2][i]= us[2][i + 1] + 1;
if(pai[i] < 3) continue;
us[3][i]= us[3][i + 1] + 1;
}
// DP出可行的顺子长度
for(int i= ls; i < v.size(); i++) {
if(v[i].siz > nown) continue;
switch(v[i].typ) {
case SHUNZI: {
if(v[i].r - v[i].l + 1 > us[v[i].k1][v[i].l]) break;
for(int j= v[i].l; j <= v[i].r; j++) pai[j]-= v[i].k1;
dfs(nown - v[i].siz, nowa + 1, i + 1);
for(int j= v[i].l; j <= v[i].r; j++) pai[j]+= v[i].k1;
// 判断顺子
break;
}
case SANDAI: {
if(pai[v[i].l] < 3 || pai[v[i].k1] < v[i].r) break;
pai[v[i].l]-= 3, pai[v[i].k1]-= v[i].r;
dfs(nown - v[i].siz, nowa + 1, i + 1);
pai[v[i].l]+= 3, pai[v[i].k1]+= v[i].r;
// 判断三带
break;
}
case SIDAI: {
if(pai[v[i].l] < 4) break;
if(pai[v[i].k1] < 1 || pai[v[i].k2] < 1) break;
if(v[i].r == 2 && (pai[v[i].k1] < 2 || pai[v[i].k2] < 2)) break;
// 都需要两张
if(v[i].r == 2 && v[i].k1 == v[i].k2 && pai[v[i].k1] < 4) break;
// 两对相同数码
if(v[i].r == 1 && v[i].k1 == v[i].k2 && pai[v[i].k1] < 2) break;
// 两张相同数码
pai[v[i].l]-= 4;
pai[v[i].k1]-= v[i].r;
pai[v[i].k2]-= v[i].r;
dfs(nown - v[i].siz, nowa + 1, i + 1);
pai[v[i].l]+= 4;
pai[v[i].k1]+= v[i].r;
pai[v[i].k2]+= v[i].r;
// 判断四带
}
default: break;
}
}
return;
}
int main() {
scanf("%d%d", &T, &n);
while(T--) {
memset(pai, 0, sizeof(pai)), bestans= 0x3f3f3f3f;
for(int i= 1; i <= n; i++) {
scanf("%d%d", &ps[i].num, &ps[i].col);
if(ps[i].num == 1) ps[i].num= 14;
// 1 当 14
if(ps[i].num == 0) ps[i].num= ps[i].col + 14;
// 大小王当15、16
++pai[ps[i].num];
}
memset(us3, 0, sizeof(us3)), memset(us2, 0, sizeof(us2)), memset(us1, 0, sizeof(us1));
v.clear();
for(int i= 14; i >= 3; i--) {
if(pai[i] < 1) continue;
us1[i]= us1[i + 1] + 1;
if(pai[i] < 2) continue;
us2[i]= us2[i + 1] + 1;
if(pai[i] < 3) continue;
us3[i]= us3[i + 1] + 1;
}
// DP出顺子长度
for(int i= 2; i <= 16; i++) {
for(int j= 5; j <= us1[i]; j++) v.push_back(CP(SHUNZI, j, i, i + j - 1, 1));
for(int j= 3; j <= us2[i]; j++) v.push_back(CP(SHUNZI, j * 2, i, i + j - 1, 2));
for(int j= 2; j <= us3[i]; j++) v.push_back(CP(SHUNZI, j * 3, i, i + j - 1, 3));
// i 当左端点的顺子
if(pai[i] < 3) continue;
for(int j= 2; j <= 16; j++) {
if(i == j || !pai[j]) continue;
v.push_back(CP(SANDAI, 4, i, 1, j));
if(pai[j] < 2) continue;
v.push_back(CP(SANDAI, 5, i, 2, j));
}
// 三带
if(pai[i] < 4) continue;
for(int j= 2; j <= 16; j++) {
if(i == j || !pai[j]) continue;
for(int k= j + 1; k <= 16; k++) {
if(i == k || !pai[k]) continue;
v.push_back(CP(SIDAI, 6, i, 1, j, k));
if(pai[j] < 2 || pai[k] < 2) continue;
v.push_back(CP(SIDAI, 8, i, 2, j, k));
}
if(pai[j] == 4) v.push_back(CP(SIDAI, 8, i, 2, j, j));
if(pai[j] > 2) v.push_back(CP(SIDAI, 6, i, 1, j, j));
}
// 四带
}
sort(v.begin(), v.end());
// 排序
dfs(n, 0, 0);
cout << bestans << endl;
}
return 0;
}
···