tyvj 2002 扑克牌
2024-09-04 02:50:46
期望DP
本题递推比较麻烦,可以记忆化搜索
注意搜索的边界条件
以及每一次转移
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
double dp[16][16][16][16][6][6];
bool f[16][16][16][16][6][6];
int term[4];
double dfs(int a, int b, int c, int d, int p, int q) {
if(f[a][b][c][d][p][q]) return dp[a][b][c][d][p][q];
f[a][b][c][d][p][q] = 1;
double & ans = dp[a][b][c][d][p][q];ans = 0.0;
int r1 = a, r2 = b, r3 = c, r4 = d;
if(p == 1) r1++; if(p == 2) r2++; if(p == 3) r3++; if(p == 4) r4++;
if(q == 1) r1++; if(q == 2) r2++; if(q == 3) r3++; if(q == 4) r4++;
if(r1 >= term[0] && r2 >= term[1] && r3 >= term[2] && r4 >= term[3]) return ans = 0;
int sum = 54 - r1 - r2 - r3 - r4;
if(sum <= 0) return ans = 1e10;
if(a < 13) ans += dfs(a + 1, b, c, d, p, q) * (13 - a) /sum;
if(b < 13) ans += dfs(a, b + 1, c, d, p, q) * (13 - b) /sum;
if(c < 13) ans += dfs(a, b, c + 1, d, p, q) * (13 - c) /sum;
if(d < 13) ans += dfs(a, b, c, d + 1, p, q) * (13 - d) /sum;
if(!p) {
double tmp = dfs(a, b, c, d, 1, q);
tmp = min(tmp, dfs(a, b, c, d, 2, q));
tmp = min(tmp, dfs(a, b, c, d, 3, q));
tmp = min(tmp, dfs(a, b, c, d, 4, q));
ans += tmp / sum;
}
if(!q) {
double tmp = dfs(a, b, c, d, p, 1);
tmp = min(tmp, dfs(a, b, c, d, p, 2));
tmp = min(tmp, dfs(a, b, c, d, p, 3));
tmp = min(tmp, dfs(a, b, c, d, p, 4));
ans += tmp / sum;
}
ans += 1.0;//概率和是 1 ,所以我们直接加 1 即可
return ans;
}
int main() {
for(int i = 0; i < 4; i++) cin >> term[i];
double ans = dfs(0, 0, 0, 0, 0, 0);
if(ans >= 100.0) printf("-1.000\n");
else printf("%.3f\n", ans);
return 0;
}
最新文章
- 集合的扩展方法ForEach的使用
- Threading in C#
- el表达式获取cookie
- CentOS 6.3 源码安装LAMP(Linux+Apache+Mysql+Php)环境
- APMServ—我用过的最优秀的PHP集成环境工具
- 第二次作业-关于Steam游戏平台的简单分析
- day13
- 从零开始在iPhone上运行视频流实时预测模型应用,只需10步
- okHttp超时报错解决方案
- CF367C. Hard problem
- vue-cli webpack 全局引用jquery
- [AWS] Deploy react project on EC2
- Prometheus监控学习笔记之教程推荐
- [leetcode]123. Best Time to Buy and Sell Stock III 最佳炒股时机之三
- 12、利用docker快速搭建Wordpress网站
- Tomcat源码学习(1)
- Selenium2+python自动化48-登录方法(参数化)
- samba安装测试
- django基础复习
- Centos7 下安装以及使用mssql