给一组扑克牌，按照斗地主的规则出牌，求最少多少次出完。
链接
题解
以每种点数的牌的数量为状态（状态可压缩进一个 64 位整数中），搜索。
代码
#include <cstdio>
#include <climits>
#include <vector>
#include <algorithm>
const int MAXN = 13;
const int CARD_JOKER = 0;
const int CARD_2 = 1;
const int CARD_3 = 2;
const int CARD_4 = 3;
const int CARD_5 = 4;
const int CARD_6 = 5;
const int CARD_7 = 6;
const int CARD_8 = 7;
const int CARD_9 = 8;
const int CARD_10 = 9;
const int CARD_J = 10;
const int CARD_Q = 11;
const int CARD_K = 12;
const int CARD_A = 13;
typedef unsigned long long Status;
inline int id(const int x) {
if (x == 1) return 13;
return (x >= 2 && x <= 13) ? (x - 1) : x;
}
inline int get(const Status &s, const int index) {
return (s >> (index << 2)) & 15ll;
}
#ifdef DBG
inline void print(const Status &s, const bool newLine = true) {
// for (int i = 0; i < 64; i++) putchar((s & (1ll << i)) ? '1' : '0');
for (int i = 0; i < 14; i++) printf("%d ", get(s, i));
if (newLine) putchar('\n');
}
#endif
inline void set(Status &s, const int index, const int val) {
/*
if (val < 0) {
puts("???");
}
*/
#ifdef DBG
print(s, false);
printf("=> ");
#endif
s &= ~(15ll << (index << 2));
s |= (val & 15ll) << (index << 2);
#ifdef DBG
print(s);
#endif
}
inline void change(Status &s, const int index, const int delta) {
set(s, index, get(s, index) + delta);
}
int n, ans;
// std::tr1::unordered_map<Status, int> map;
struct HashMap {
const static int HASH_SIZE = 7979717;
struct Node {
Status key;
int val, time;
} N[HASH_SIZE];
int time;
HashMap() : time(1) {}
int locate(const Status &key) {
int i;
for (i = key % HASH_SIZE; N[i].time == time && N[i].key != key; (i < HASH_SIZE - 1) ? (i++) : (i = 0));
if (N[i].time != time) {
N[i].time = time;
N[i].key = key;
N[i].val = INT_MAX;
}
return i;
}
int &operator[](const Status &key) {
return N[locate(key)].val;
}
void clear() {
time++;
}
} map;
inline void search(const Status &s, const int step = 0) {
#ifdef DBG
print(s, false);
printf("[%d, %d]\n", step, ans);
#endif
if (step >= ans) return;
int &x = map[s];
if (step >= x) return;
x = step;
/*
std::tr1::unordered_map<Status, int>::iterator it = map.find(s);
if (it != map.end() && step >= it->second) return;
map[s] = step;
*/
if (!s) {
ans = step;
return;
}
// 333 444
for (int i = CARD_3; i <= CARD_K; i++) {
Status next = s;
int x = get(next, i);
if (x < 3) {
continue;
} else set(next, i, x - 3);
for (int j = i + 1; j <= CARD_A; j++) {
int x = get(next, j);
if (x < 3) {
break;
} else {
set(next, j, x - 3);
search(next, step + 1);
}
}
}
// 33 44 55
for (int i = CARD_3; i <= CARD_Q; i++) {
bool valid = true;
Status next = s;
for (int j = i; j < i + 2; j++) {
int x = get(next, j);
if (x < 2) {
valid = false;
break;
} else set(next, j, x - 2);
}
if (!valid) continue;
for (int j = i + 2; j <= CARD_A; j++) {
int x = get(next, j);
if (x < 2) {
break;
} else {
set(next, j, x - 2);
search(next, step + 1);
}
}
}
// 3 4 5 6 7
for (int i = CARD_3; i <= CARD_10; i++) {
bool valid = true;
Status next = s;
for (int j = i; j < i + 4; j++) {
int x = get(next, j);
if (x < 1) {
valid = false;
break;
} else set(next, j, x - 1);
}
if (!valid) continue;
for (int j = i + 4; j <= CARD_A; j++) {
int x = get(next, j);
if (x < 1) {
break;
} else {
set(next, j, x - 1);
search(next, step + 1);
}
}
}
std::vector<int> four, three, two, one;
for (int i = CARD_JOKER; i <= CARD_A; i++) {
int x = get(s, i);
if (x == 4) four.push_back(i);
else if (x == 3) three.push_back(i);
else if (x == 2) two.push_back(i);
else if (x == 1) one.push_back(i);
}
// 2222 [3 4] / 2222 [33 44]
for (std::vector<int>::const_iterator it = four.begin(); it != four.end(); it++) {
Status tmp = s;
set(tmp, *it, 0);
for (std::vector<int>::const_iterator a = two.begin(); a != two.end(); a++) {
if (*a == 0) continue;
for (std::vector<int>::const_iterator b = a + 1; b != two.end(); b++) {
if (*b == 0) continue;
Status next = tmp;
set(next, *a, 0);
set(next, *b, 0);
search(next, step + 1);
}
for (std::vector<int>::const_iterator b = three.begin(); b != three.end(); b++) {
Status next = tmp;
change(next, *a, -2);
change(next, *b, -2);
search(next, step + 1);
}
Status next = tmp;
set(next, *a, 0);
search(next, step + 1);
}
for (std::vector<int>::const_iterator a = four.begin(); a != four.end(); a++) {
if (*a == *it) continue;
Status next = tmp;
set(next, *a, 0);
search(next, step + 1);
}
for (std::vector<int>::const_iterator a = one.begin(); a != one.end(); a++) {
for (std::vector<int>::const_iterator b = a + 1; b != one.end(); b++) {
Status next = tmp;
set(next, *a, 0);
set(next, *b, 0);
search(next, step + 1);
}
for (std::vector<int>::const_iterator b = three.begin(); b != three.end(); b++) {
Status next = tmp;
change(next, *a, -1);
change(next, *b, -1);
search(next, step + 1);
}
}
search(tmp, step + 1);
}
// 222 [3] / 222 [33]
for (std::vector<int>::const_iterator it = three.begin(); it != three.end(); it++) {
Status tmp = s;
set(tmp, *it, 0);
for (std::vector<int>::const_iterator a = three.begin(); a != three.end(); a++) {
if (*a == *it) continue;
Status next = tmp;
change(next, *a, -1);
search(next, step + 1);
change(next, *a, -1);
search(next, step + 1);
}
for (std::vector<int>::const_iterator a = two.begin(); a != two.end(); a++) {
if (*a == 0) {
// Take only one joker
Status next = tmp;
set(next, *a, 1);
search(next, step + 1);
continue;
}
Status next = tmp;
set(next, *a, 0);
search(next, step + 1);
}
for (std::vector<int>::const_iterator a = one.begin(); a != one.end(); a++) {
Status next = tmp;
set(next, *a, 0);
search(next, step + 1);
}
search(tmp, step + 1);
}
// 22
for (std::vector<int>::const_iterator it = two.begin(); it != two.end(); it++) {
Status next = s;
set(next, *it, 0);
search(next, step + 1);
}
// 2
for (std::vector<int>::const_iterator it = one.begin(); it != one.end(); it++) {
Status next = s;
set(next, *it, 0);
search(next, step + 1);
}
}
int main() {
int t;
scanf("%d %d", &t, &n);
while (t--) {
Status init = 0;
for (int i = 0; i < n; i++) {
int a, b;
scanf("%d %d", &a, &b);
change(init, id(a), 1);
}
map.clear();
ans = INT_MAX;
search(init);
printf("%d\n", ans);
}
return 0;
}