题解

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define INF 1061109567
#define Re register

using namespace std;

int t, n, f[25][25][25][25][5], cnt[5], card[25], num, ans;

inline int dfs2(int on, int tw, int th, int fl, int w) {
if (f[on][tw][th][fl][w] < INF) {
return f[on][tw][th][fl][w]; }
f[on][tw][th][fl][w] = on + tw + th + fl + w;
int &now = f[on][tw][th][fl][w];
if (w == 2) now = min(now, dfs2(on, tw, th, fl, 0) + 1);
if (fl) {
if (tw >= 2) now = min(now, dfs2(on, tw - 2, th, fl - 1, w) + 1);
//直接四带二对
if (tw) now = min(now, dfs2(on, tw - 1, th, fl - 1, w) + 1);
//四带两张一样的
if (w == 2) now = min(now, dfs2(on, tw, th, fl - 1, 0) + 1);
//王炸组四带二张
if (w && on) now = min(now, dfs2(on - 1, tw, th, fl - 1, w - 1) + 1);
//单王加单牌组四带二
if (on >= 2) now = min(now, dfs2(on - 2, tw, th, fl - 1, w) + 1);
//直接四带二张
now = min(now, dfs2(on + 1, tw, th + 1, fl - 1, w));
//拆成三与一
now = min(now, dfs2(on, tw + 2, th, fl - 1, w));
//拆成两对
now = min(now, dfs2(on + 2, tw + 1, th, fl - 1, w));
//拆成一对加两张
}
if (th) {
if (tw) now = min(now, dfs2(on, tw - 1, th - 1, fl, w) + 1);
//直接三带二
if (w) now = min(now, dfs2(on, tw, th - 1, fl, w - 1) + 1);
//三带一王
if (on) now = min(now, dfs2(on - 1, tw, th - 1, fl, w) + 1);
//三带一单
now = min(now, dfs2(on + 1, tw + 1, th - 1, fl, w));
//拆牌成一单一对
now = min(now, dfs2(on + 3, tw, th - 1, fl, w));
//拆牌成三张单
}
return f[on][tw][th][fl][w]; }

inline int get() {
memset(cnt, 0, sizeof(cnt));
for (Re int i = 1; i <= 13; i++) cnt[card[i]]++;
return dfs2(cnt[1], cnt[2], cnt[3], cnt[4], card[14]); }

inline void dfs1(int step) {
ans = min(ans, step + get());
bool flag;
for (Re int i = 1; i <= 11; i++) {
for (Re int j = 2; j <= 12; j++) {
if (i + j - 1 > 12) break;
flag = true;
for (Re int k = 0; k <= j - 1; k++) {
if (card[i + k] < 3) flag = false; }
if (!flag) break;
for (Re int k = 0; k <= j - 1; k++) card[i + k] -= 3;
dfs1(step + 1);
for (Re int k = 0; k <= j - 1; k++) card[i + k] += 3; } }
for (Re int i = 1; i <= 10; i++) {
for (Re int j = 3; j <= 12; j++) {
if (i + j - 1 > 12) break;
flag = true;
for (Re int k = 0; k <= j - 1; k++) {
if (card[i + k] < 2) flag = false; }
if (!flag) break;
for (Re int k = 0; k <= j - 1; k++) card[i + k] -= 2;
dfs1(step + 1);
for (Re int k = 0; k <= j - 1; k++) card[i + k] += 2; } }
for (Re int i = 1; i <= 8; i++) {
for (Re int j = 5; j <= 12; j++) {
if (i + j - 1 > 12) break;
flag = true;
for (Re int k = 0; k <= j - 1; k++) {
if (!card[i + k]) flag = false; }
if (!flag) break;
for (Re int k = 0; k <= j - 1; k++) card[i + k] -= 1;
dfs1(step + 1);
for (Re int k = 0; k <= j - 1; k++) card[i + k] += 1; } } }

inline void solve() {
memset(card, 0, sizeof(card));
for (int i = 1; i <= n; i++) {
int type, col;
cin >> type >> col;
if (type == 0) type = 14;
else if (type == 1 || type == 2) type += 11;
else if (type >= 3 && type <= 13) type -= 2;
card[type]++; }
num = 0, ans = n;
dfs1(0);
cout << ans << endl; }

int main() {
ios::sync_with_stdio(false);
memset(f, 63, sizeof(f));
cin >> t >> n;
for (int i = 1; i <= t; i++) solve();
return 0; }