UVa1637 Double Patience

原题链接：UVa1637

解析：一开始用的是深搜，但是超时了，明显我没计算好时间。然后尝试用记忆化处理，但是状态我却没法表示，事实上用map<vector<int>,double> d 可以把数组当作一个状态来表示是否已经搜索过。那么这个d的第二个位置表示的就是当前状态成功率，如果不能成功呢，就存储0（也就是当前状态不能再消掉牌），如果所有牌都消掉了呢，就返回1,（百分百成功）。如果当前状态有total种消法，每种消法有不同成功率，那么当前成功率就是这total种方法的平均值。

代码实例：

#include<iostream>
#include<cstring>
#include<map>
#include<vector>
#include<cstdio>
using namespace std;
map<vector<int>,double> d;
char card[9][4][3];
double dfs(int res,vector<int>& num){
	if(res == 0)	return 1;
	if(d.count(num) != 0)	return d[num];
	double sum = 0;
	double total = 0;
	for(int i = 0;i < 9;i++){
		if(num[i] == 0)	continue;
		char c = card[i][num[i]-1][0];
		for(int j = i+1;j < 9;j++){
			if(num[j] != 0)
			if(c == card[j][num[j]-1][0]){
				total++;
				num[i]--;
				num[j]--;
				sum += dfs(res-1,num);
				num[i]++;
				num[j]++;
			}
		}
	}
	if(total == 0)	return d[num] = 0;
	else return d[num] = sum/total;
}
bool read_input() {
  for(int i = 0; i < 9; i++)
    for(int j = 0; j < 4; j++)
      if(scanf("%s", card[i][j]) != 1) return false;
  return true;
}
int main()
{
	while(read_input()){
		d.clear();
		vector<int> num(9,4);
		printf("%.6lf
",dfs(18,num));	
	}
	
	return 0;
}