题链：
http://poj.org/problem?id=2794
题解：
状压DP，概率
9元组表示每一堆还剩几张牌。可以用5进制状压，共5^9=1953124个状态。
令P(S)表示S这个状态被取完的概率。
假设当前状态为S，可以有三种取法，分别对应转移到_S1,_S2,_S3三个更小的状态。
那么由全概率公式：
如果_S1状态为前提条件，那么S就有1/3的概率转移到_S1
同理_S2,_S3。所以得出:
P(S)=P(S|_S1)*P(_S1)+P(S|_S2)*P(_S2)+P(S|_S3)*P(_S3)
由于P(S|_S1=)P(S|_S2)=P(S|_S3)=1/3
所以P(S)=(P(_S1)+P(_S2)+P(_S3))/3
即每个状态的概率为其后继状态的平均值。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char card[10][5];
bool vis[2000000];
double dp[2000000];
int code(int *a){
static int s; s=0;
for(int i=9;i>=1;i--)
s=s*5+a[i];
return s;
}
void decode(int s,int *a){
for(int i=1;i<=9;i++)
a[i]=s%5,s/=5;
}
double DP(int s){
if(vis[s]) return dp[s];
vis[s]=1;
int a[10],cnt=0; decode(s,a);
for(int i=1;i<=9;i++)
for(int j=i+1;j<=9;j++){
if(!a[i]||!a[j]||card[i][a[i]]!=card[j][a[j]]) continue;
a[i]--; a[j]--; cnt++;
int _s=code(a);
dp[s]+=DP(_s);
a[i]++; a[j]++;
}
if(cnt) dp[s]/=cnt;
return dp[s];
}
int main(){
static char S[5];
for(int i=1;i<=9;i++)
for(int j=1;j<=4;j++)
scanf("%s",S),card[i][j]=S[0];
vis[0]=1; dp[0]=1;
printf("%.6lf
",DP(1953124));
return 0;
}