记录编号	469375	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]斗地主	最终得分	100
用户昵称	panda_2134	是否通过	通过
代码语言	C++	运行时间	0.693 s
提交时间	2017-11-03 07:54:47	内存使用	0.32 MiB

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f, w[] = {14, 12, 13, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }; //权重
int T, N, Ans, cd[20];
void Init() {
	int t = 0, c = 0;
	for (int i = 1; i <= N; i++) {
		scanf("%d%d", &t, &c);
		cd[w[t]]++;
	}
}
/*
	单独估计打单牌的代价
	总结：对于暴搜类问题，当搜索对象先后顺序无关紧要时，
	如果某几类分支的限制条件过少，导致分支众多，就考虑
	能否一次性地合并处理，把多个分支变为一个估价函数，
	也就是在靠近答案时一并计算贡献。 
*/
inline int h() {
	int ret=0;
	for (int i = 1; i <= 14; i++) {
		int t = cd[i];
		ret += t/4; t %= 4;
		ret += (bool)t;
	}
	return ret;
}
void DFS(int st) {
	if (st >= Ans) return;
	Ans=min(Ans, st+h()); //打单牌/全打完 
	//四带二-1
	for (int i = 1; i <= 14; i++) {
		if (cd[i] >= 4) {
			cd[i] -= 4;
			for (int j = 1; j <= 14; j++) if (cd[j]) {
					cd[j]--;
					for (int k = 1; k <= 14; k++) if (cd[k]) {
							cd[k]--;
							DFS(st + 1);
							cd[k]++;
						}
					cd[j]++;
				}
			cd[i] += 4;
		}
	}
	//四带二-2
	for (int i = 1; i <= 14; i++) {
		if (cd[i] >= 4) {
			cd[i] -= 4;
			for (int j = 1; j <= 14; j++) if (cd[j] >= 2) {
					cd[j]-=2;
					for (int k = 1; k <= 14; k++) if (cd[k] >= 2) {
							cd[k]-=2;
							DFS(st + 1);
							cd[k]+=2;
						}
					cd[j]+=2;
				}
			cd[i] += 4;
		}
	}
	//三顺子 不包括13,14
	for (int i = 1; i <= 12; i++) {
		int j;
		for (j = i; cd[j] >= 3 && j <= 12; j++); //[i,j)
		if (j - i >= 2) {
			for (int k = i; k < j; k++) cd[k] -= 3;
			DFS(st + 1);
			for (int k = i; k < j; k++) cd[k] += 3;
		}
	}
	//双顺子
	for (int i = 1; i <= 12; i++) {
		int j;
		for (j = i; cd[j] >= 2 && j <= 12; j++);
		if (j - i >= 3) {
			for (int k = i; k < j; k++) cd[k] -= 2;
			DFS(st + 1);
			for (int k = i; k < j; k++) cd[k] += 2;
		}
	}
	//单顺子
	for (int i = 1; i <= 12; i++) {
		int j;
		for (j = i; cd[j] >= 1 && j <= 12; j++);
		if (j - i >= 5) {
			for (int k = i; k < j; k++) cd[k]--;
			DFS(st + 1);
			for (int k = i; k < j; k++) cd[k]++;
		}
	}
	//三带二
	for (int i = 1; i <= 14; i++) if (cd[i] >= 3) {
			cd[i] -= 3;
			for (int j = 1; j <= 14; j++) if (cd[j] >= 2) {
					cd[j] -= 2;
					DFS(st + 1);
					cd[j] += 2;
				}
			cd[i] += 3;
		}
	//三带一
	for (int i = 1; i <= 14; i++) if (cd[i] >= 3) {
			cd[i] -= 3;
			for (int j = 1; j <= 14; j++) if (cd[j] >= 1) {
					cd[j]--;
					DFS(st + 1);
					cd[j]++;
				}
			cd[i] += 3;
		}
}
void Work() {
	//预处理上界
	//贪心打牌
	Ans=h();

	DFS(0);

	printf("%d", Ans);
	if (T) putchar(10);
}
void Clear() {
	memset(cd, 0, sizeof(cd)); Ans = 0;
}
int main() {
	freopen("landlords.in", "r", stdin);
#ifndef DEBUG
	freopen("landlords.out", "w", stdout);
#endif
	scanf("%d%d", &T, &N);
	while (T--) {
		Init(); Work(); Clear();
	}
	return 0;
}