一道记忆化搜索

原题链接

和着色方案很像，这里就不详细阐述，可以去我博客里的着色方案里看。

但要注意本题不一样的是同种面值的牌花色不同，所以在转移时还需要乘上同种面值的牌的个数。

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ull;

const int N = 14;

ull f[N][N][N][N][5];

int v[N], S[5];

int re()

{

	int x = 0;

	char c = getchar();

	bool p = 0;

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

		p = (c == '-' || p) ? 1 : 0;

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

		x = x * 10 + (c - '0');

	return p ? -x : x;

}

int re_l()

{

	char c = getchar();

	for (; (c<'2' || c>'9') && c != 'T'&&c != 'J'&&c != 'Q'&&c != 'K'&&c != 'A'; c = getchar());

	if (c == 'T')

		return 10;

	if (c == 'J')

		return 11;

	if (c == 'Q')

		return 12;

	if (c == 'K')

		return 13;

	if (c == 'A')

		return 1;

	return c - '0';

}

ull dp(int a, int b, int c, int d, int la)

{

	ull s = 0, &k = f[a][b][c][d][la];

	if (k)

		return k;

	if (!(a | b | c | d))

		return 1;

	if (a)

		s += 1llu * (a - (la == 2))*dp(a - 1, b, c, d, 1);

	if (b)

		s += (1llu * (b - (la == 3))*dp(a + 1, b - 1, c, d, 2)) << 1;

	if (c)

		s += 1llu * (c - (la == 4))*dp(a, b + 1, c - 1, d, 3) * 3;

	if (d)

		s += (1llu * d*dp(a, b, c + 1, d - 1, 4)) << 2;

	return k = s;

}

int main()

{

	int i, j, n, t;

	t = re();

	for (j = 1; j <= t; j++)

	{

		n = re();

		memset(v, 0, sizeof(v));

		memset(S, 0, sizeof(S));

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

			v[re_l()]++;

		for (i = 1; i <= 13; i++)

			S[v[i]]++;

		printf("Case #%d: %llu\n", j, dp(S[1], S[2], S[3], S[4], 0));

	}

	return 0;

}