题意:

一共有9堆牌,每堆牌四张。每次可以取堆顶点数相同的两张牌,如果有多种方案则选取是随机的。

如果最后将所有牌取完,则视为游戏胜利,求胜利的概率。

分析:

用一个九元组表示状态,分别代表每堆牌剩余的牌数。根据全概率公式,d[i]为后继状态成功概率的平均值。

 #include <iostream>
#include <cstdio>
#include <map>
#include <vector>
using namespace std; map<vector<int>, double> d;
char card[][][]; double dp(vector<int>& cnt, int c)
{
if(c == ) return ; //所有的牌取完,游戏胜利概率为1
if(d.count(cnt) != ) return d[cnt];
double sum = ; //后继状态的总概率
int tot = ; //后继状态的数量
for(int i = ; i < ; ++i) if(cnt[i] > )
for(int j = i + ; j < ; ++j) if(cnt[j] > )
if(card[i][cnt[i]-][] == card[j][cnt[j]-][])
{
tot++;
cnt[i]--, cnt[j]--;
sum += dp(cnt, c-);
cnt[i]++, cnt[j]++;
}
if(tot == ) return d[cnt] = ;
return d[cnt] = sum / tot;
} bool read()
{
for(int i = ; i < ; ++i)
for(int j = ; j < ; ++j)
if(scanf("%s", card[i][j]) != )
return false;
return true;
} int main()
{
//freopen("in.txt", "r", stdin);
while(read())
{
vector<int> cnt(, );
d.clear();
printf("%.6f\n", dp(cnt, ));
} return ;
}

代码君

最新文章

  1. Silverlight5中横向显示ListBox
  2. 《Linux内核设计与实现》CHAPTER5阅读梳理
  3. 关于Python中输出中文的一点疑问
  4. 线性函数拟合R语言示例
  5. Win32下 Qt与Lua交互使用(二):在Lua脚本中使用Qt类
  6. redis多数据库操作
  7. java 并发多线程显式锁概念简介 什么是显式锁 多线程下篇(一)
  8. 关于如何使用xposed来hook某支付软件
  9. UEditor之实现配置简单的图片上传示例 转
  10. SDK更新
  11. 数据库事务的隔离以及spring的事务传播机制
  12. BN_batch normalization
  13. linux 环境下如何完全卸载postgres
  14. loadrunner http协议性能测试脚本编写
  15. Dapper使用总结
  16. zabbix已恢复正常,但是报警信息一直出现,求大佬解答。
  17. 【原创】关于程序卸载的一个Bug
  18. Java 容器源码分析之HashMap多线程并发问题分析
  19. Active Directory 域服务(AD DS)
  20. Centos7.3防火墙配置

热门文章

  1. 多线程的单元测试工具 - GroboUtils
  2. ubuntu14.04 中文输入法无法使用
  3. Android UI学习1:控件和基本事件的响应
  4. Oracle查看用户所在表空间
  5. EXTJS4.2 控件之Grid 根据数据源某列数据不同绑定不同的控件setEditor
  6. Java中的IO流系统详解
  7. 【BZOJ 1084】[SCOI2005]最大子矩阵
  8. mybatis的javaType和ofType
  9. JS日期格式化(网上转载)
  10. BZOJ 1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果