[Uva1637][DFS][记忆化] 纸牌游戏 Double Patience

写代码一定要注意!!!!!!

我因为i+1写成了1+1改了一晚上!!!!!!(菜都写脸上了)

题目:

double patience是一种单人游戏，使用标准的36张牌组。这些牌在洗牌后放在一张桌子上，叠成9叠，每叠4张，面朝上。

牌放下后，玩家转身。每一次，他可以从任意两个牌堆中取出同一等级的*牌，然后将它们移除。如果有几种可能性，玩家可以选择任何一种。如果所有的牌都从桌上移除，玩家将赢得游戏，如果一些牌仍然在桌上，并且没有有效的移动，玩家将失败。

乔治喜欢这种游戏。但当有几种可能时，他不知道要选择哪一张。乔治不想多想，所以在这种情况下，他只需从可能的情况中选择一对随机的，并删除它。乔治选择每种情况的可能性相同。

例如，如果最上面的牌是ks、kh、kd、9h、8s、8d、7c、7d和6h，他会删除任何一对在(ks, kh)、(ks, kd)、(kh, kd)、 (8s, 8d)和 (7c, 7d)中的任何一对。删除（ks,kh）、（ks,kd）、（kh,kd）、（8s,8d）和（7c,7d）的概率都为1/5。

请算出在游戏开始时，根据桌上的牌，找出如果乔治按照描述行事，他赢得游戏的可能.

 

大概意思就是说有 9 堆牌, 每堆 4 张, 当两堆当前最顶上纸牌相同时可以拿走, 问只要有可以拿走的纸牌就拿走, 最后能够拿完纸牌的概率有多大

这题乍一看除了搜索并没有什么思路显然是搜索题嘛

可以直接优雅简单粗暴的开一个九维(确信)数组 

ans[5][5][5][5][5][5][5][5][5]

记录一下每一种情况下的胜率

这样我们可以知道:

当牌拿完时获胜, 即 ans[0][0][0][0][0][0][0][0][0] = 1;

然后就可以写循环暴力枚举每一种情况了.

每找到一种拿牌方案, 这一层搜索的总方案数+1;

这一层搜索的胜率就是 (所有找到的方案的胜率之和) / (所有找到的方案数)

找不到方案时胜率显然是0;

然后你就会发现tle了

所以这题需要用到记忆化

一个方案如果被搜过了, 就直接返回胜率而不向下枚举

所以再开一个bool数组记录访问状态

那么边界就是没有牌的状态是访问过的(即直接返回ans[0][0][0][0][0][0][0][0][0] = 1)

这题就ac了

 

下面是代码

这题代码相当不优雅

 1 /*
 2 思路:dfs
 3 开两个九维(确信)数组,一个double型,用来记录每一堆每一层纸牌的胜率
 4 当然可以暴搜，但是会tle，所以第二个bool类型的数组便派上用场了:记忆化
 5 bool类型这个数组记录一个情况有没有经历过
 6 每一种情况的胜率:从这一种情况开始搜的胜率之和除以所有搜到的情况之和
 7 当搜到一层无法再次往下搜索时该状态胜率为0
 8 当纸牌能被搜完时胜率为1
 9 花色对结果不造成影响
10 */
11 
12 # include <cstdio>
13 # include <iostream>
14 
15 using namespace std;
16 
17 int poker[10][5]; // 九堆纸牌一堆四个
18 double ans[5][5][5][5][5][5][5][5][5];
19 bool vis[5][5][5][5][5][5][5][5][5];
20 
21 double dfs(int h1, int h2, int h3, int h4, int h5, int h6, int h7, int h8, int h9){
22     if(vis[h1][h2][h3][h4][h5][h6][h7][h8][h9])
23         return ans[h1][h2][h3][h4][h5][h6][h7][h8][h9];
24     vis[h1][h2][h3][h4][h5][h6][h7][h8][h9] = true; // 记忆化
25 
26     int height[20] = {0, h1, h2, h3, h4, h5, h6, h7, h8, h9}; // 记录每堆纸牌高度
27     
28     double sumrate = 0.0; // 记录胜率
29     double sumsol = 0; // 记录找到的取牌方法总数
30 
31     for(int i = 1; i <= 9; i++){
32         for(int j = i + 1; j <= 9; j++){
33             if(height[i] > 0 && height[j] > 0 && poker[i][height[i]] == poker[j][height[j]]){
34                 height[i] -= 1;
35                 height[j] -= 1;
36                 sumsol += 1;
37                 // if(height[1]>=0&&height[2]>=0&&height[3]>=0&&height[4]>=0&&height[5]>=0&&height[6]>=0&&height[7]>=0&&height[8]>=0&&height[9]>=0)
38                 sumrate += dfs(height[1], height[2], height[3], height[4], height[5], height[6], height[7], height[8], height[9]);
39                 height[i]++;
40                 height[j]++;
41             }
42         }
43     }
44 
45     if(sumsol > 0) return ans[h1][h2][h3][h4][h5][h6][h7][h8][h9] = sumrate / sumsol;
46     else return ans[h1][h2][h3][h4][h5][h6][h7][h8][h9];
47 }
48 
49 int main(){
50     vis[0][0][0][0][0][0][0][0][0] = 1;
51     ans[0][0][0][0][0][0][0][0][0] = 1.00;
52     char p1[3], p2[3], p3[3], p4[3];
53     for(int i = 1; i <= 9; i++){
54         cin>>p1>>p2>>p3>>p4;
55         poker[i][1] = p1[0] - '0';
56         poker[i][2] = p2[0] - '0';
57         poker[i][3] = p3[0] - '0';
58         poker[i][4] = p4[0] - '0';
59     }
60     
61     printf("%.6lf", dfs(4, 4, 4, 4, 4, 4, 4, 4, 4));
62 
63     return 0;    
64 }

就这样吧