[Uva1637][DFS][记忆化] 纸牌游戏 Double Patien…
2020-03-06 16:01:06来源:博客园 阅读 ()
[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 }
就这样吧
原文链接:https://www.cnblogs.com/Foggy-Forest/p/12425789.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- hdu1455 拼木棍(经典dfs) 2020-02-29
- BFS和队列 2020-01-18
- dfs 2019-12-27
- dfs/bfs专项训练 2019-08-16
- DFS(四):剪枝策略 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash