【UOJ #147】【NOIP 2015】斗地主

http://uoj.ac/problem/147

搜索时先枚举三顺子，双顺子和单顺子，然后贪心带牌和成三成双成单出。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int in() {

	int k = 0, fh = 1; char c = getchar();

	for(; c < '0' || c > '9'; c = getchar())

		if (c == '-') fh = -1;

	for(; c >= '0' && c <= '9'; c = getchar())

		k = (k << 3) + (k << 1) + c - '0';

	return k * fh;

}

int a[20], c[5], n, ans;

int cal() {

	memset(c, 0, sizeof(c));

	for(int i = 0; i <= 13; ++i)

		++c[a[i]];

	int ret = 0;

	while (c[4] && c[2] >= 2) --c[4], c[2] -= 2, ++ret;

	while (c[4] && c[1] >= 2) --c[4], c[1] -= 2, ++ret;

	while (c[3] && c[2]) --c[3], --c[2], ++ret;

	while (c[3] && c[1]) --c[3], --c[1], ++ret;

	return ret + c[4] + c[3] + c[2] + c[1];

}

void dfs(int step) {

	if (step >= ans) return;

	ans = min(ans, step + cal());

	int i, j, k, tail;

	j = 0;

	for(i = 2; i <= 13; ++i) {

		for(j = max(j, i); a[j] >= 3; ++j);

		for(tail = j; tail >= i + 2; --tail) {

			for(k = i; k < tail; ++k) a[k] -= 3;

			dfs(step + 1);

			for(k = i; k < tail; ++k) a[k] += 3;

		}

	}

	j = 0;

	for(i = 2; i <= 13; ++i) {

		for(j = max(j, i); a[j] >= 2; ++j);

		for(tail = j; tail >= i + 3; --tail) {

			for(k = i; k < tail; ++k) a[k] -= 2;

			dfs(step + 1);

			for(k = i; k < tail; ++k) a[k] += 2;

		}

	}

	j = 0;

	for(int i = 2; i <= 13; ++i) {

		for(j = max(j, i); a[j] >= 1; ++j);

		for(tail = j; tail >= i + 5; --tail) {

			for(k = i; k < tail; ++k) --a[k];

			dfs(step + 1);

			for(k = i; k < tail; ++k) ++a[k];

		}

	}

}

int main() {

	int T, color, num; T = in(); n = in();

	while (T--) {

		memset(a, 0, sizeof(a));

		for(int i = 1; i <= n; ++i) {

			num = in(); color = in();

			if (num == 1) num = 13;

			else if (num != 0) --num;

			++a[num];

		}

		ans = cal();

		dfs(0);

		printf("%d\n", ans);

	}

	return 0;

}

QAQ