题目大意：现有九堆牌，每堆有四张牌，每次我们可以选择不在同一堆上的顶上的两张牌消掉（如果两张牌数字相同的话），且每次随机选择，问最终将全部牌消掉的概率。注意有多组数据输入！（不要像我一样，交了好几次才发现。。。）
解：其实是很裸的dp，但是因为每次有消掉第一层第二层第三层第四层或者已经全部消光，所以我们要开一个五进制的dp，具体怎么写程序中看吧，总的复杂度应该是
O(5^9*9*9)。
程序：
#include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> #include<cstdio> using namespace std; char s[10][10][10]; int n=9,m=4,wei[1009],bin[1009]; double dp[2000009]; pair<int,int>edge[1009]; //计算这个数所代表的五进制 void calc(int now) { int tot=n-1; while (tot>=0) { wei[tot]=(now/bin[tot]); now=now%bin[tot]; tot--; } } int main() { //注意有多组数据！ while (scanf("%s",s[0][1])!=EOF) { scanf("%s%s%s",s[0][2],s[0][3],s[0][4]); for (int i=1;i<n;i++) for (int j=1;j<=m;j++) scanf("%s",s[i][j]); bin[0]=1; for (int i=1;i<=n;i++) bin[i]=bin[i-1]*(m+1); for (int i=0;i<bin[n];i++) dp[i]=0; dp[bin[n]-1]=1.0; for (int i=bin[n]-1;i>0;i--) if (dp[i]) { calc(i); int cnt=0,p=0; for (int j=0;j<n;j++) p+=m-wei[j]; for (int j=0;j<n;j++) for (int k=j+1;k<n;k++) //如果当前这两个位置的牌相同，且两个位置的牌都没有取完 if ((s[j][wei[j]][0]==s[k][wei[k]][0]) &&(wei[j]!=0)&&(wei[k]!=0)) edge[++cnt]=make_pair(j,k); //记录当前状态下，有多少种能消掉的操作。 double now=(1.0/(double)cnt)*dp[i]; for (int j=1;j<=cnt;j++) { int a=edge[j].first,b=edge[j].second; int sum=i-bin[a]-bin[b]; dp[sum]+=now; } } printf("%.6lf\n",dp[0]); } return 0; }