UVA1637 Double Patience 纸牌游戏(NEERC 2005)

传送


因为数据很小，可以直接搞一个(5^9)个状态的暴力进行dp。

题解说可以用记忆化优化，没想出来，因为每一个状态的出边不知道怎么在记忆化的同时得到。

因为dp是DAG，所以我就建图然后拓扑了。但如果暴力(9^2*5^9)建图会超时，因为有建立了很多不会访问到的点，于是就改成了记忆化dfs建图 。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("") 
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 12;
const int maxm = 6;
const int maxs = 2e6 + 5;
In ll read()
{
	ll ans = 0;
	char ch = getchar(), las = ' ';
	while(!isdigit(ch)) las = ch, ch = getchar();
	while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
	if(las == '-') ans = -ans;
	return ans;
}
In void write(ll x)
{
	if(x < 0) x = -x, putchar('-');
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
}

char s[4];
int n, m, N, a[maxn][maxm];

int H[400], p[maxn];
In void init()
{
	for(int i = 0; i < 10; ++i) H['0' + i] = i;
	H['T'] = 10, H['J'] = 11, H['Q'] = 12, H['K'] = 13, H['A'] = 14;
	p[0] = 1;
	for(int i = 1; i <= n; ++i) p[i] = p[i - 1] * 5;
}

In int D(int x, int k) {return x % p[k + 1] / p[k];}

bool vis[maxs];
int du[maxs], c[maxs];
vector<int> v[maxs];
In void buildGraph(int S)
{
	if(vis[S]) return;
	vis[S] = 1;
	for(int i = 0; i < n; ++i)
		for(int j = i + 1; j < n; ++j)
		{
			int s1 = D(S, i), s2 = D(S, j);
			if(s1 && s2 && a[i + 1][s1] == a[j + 1][s2])
			{
				int S2 = S - p[i] - p[j];
				v[S].push_back(S2);
				du[S2]++, c[S]++;	
				buildGraph(S2);
			} 
		}
}

db dp[maxs];
In db topo()
{
	dp[N] = 1;
	queue<int> q;
	for(int i = 0; i <= N; ++i) if(!du[i]) q.push(i);
	while(!q.empty())
	{
		int now = q.front(); q.pop();
		for(auto y : v[now])
		{
			dp[y] += dp[now] * (1.0 / c[now]);
			if(!--du[y]) q.push(y);
		}
	}
	return dp[0];
}

In void Clear()
{
	Mem(vis, 0);
	Mem(du, 0), Mem(c, 0), Mem(dp, 0);
}

int main()
{
//	MYFILE();
	n = 9, m = 4, N = 1953124;
	init();
	while(scanf("%s", s) != EOF)
	{
		Clear();
		a[1][1] = H[s[0]];
		for(int i = 1; i <= n; ++i)
			for(int j = (i - 1) ? 1 : 2; j <= m; ++j)
			{
				scanf("%s", s);
				a[i][j] = H[s[0]];
			}
		buildGraph(N);
		printf("%.6lf
", topo());
	}
	return 0;
}