概率DP (由一道绿题引起的若干问题。目前为一些老题,蒟蒻的尝试学习1.0)

本文主要是介绍概率DP (由一道绿题引起的若干问题。目前为一些老题,蒟蒻的尝试学习1.0),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

概率DP:
利用动态规划去解决 概率 期望 的题目。

概率DP 求概率(采用顺推)

从 初始状态推向结果,同一般的DP类似,只是经历了概率论知识的包装。
老题:
添加链接描述
题意:
袋子里有w只白鼠,b只黑鼠,A和B轮流从袋子里抓,谁先抓到白色谁就赢。A每次随机抓一只,B每次随机 抓完一只后 会有另外一只随机老鼠跑出来。如果两个人都没有抓到白色,那么B赢。A先抓,问A赢得概率。
w b 均在1e3以内。
思考:求A赢得概率,和当前袋子中 白鼠 黑鼠得数量有关系。 所以 这个要作为状态量。一般问什么,就设计什么状态。
状态:
dp[i][j]表示 当前 袋中有 i只白鼠 和j 只黑鼠时,A获胜得概率。
起点:dp[0][i]=0,dp[i][0]=1;
终点:dp[w][b]
转移:
1.先手拿到白鼠 dp[i][j]+=i/(i+j)
2.先手黑鼠,后手白鼠 f[i][j]+=0 这种情况不用处理
3.先手黑鼠,后手黑鼠,跑掉白鼠
f[i][j]+=j/(i+j)*(j-1)(i+j-1)i(i+j-2)dp[i-1][j-2]
4.先手黑鼠,后手黑鼠,跑黑鼠:dp[i][j]+=j/(i+j)
(j-1)/(i+j-1)
(j-2)/(i+j-2)*dp[i][j-3];

#include <bits/stdc++.h>
using namespace std;
void solve()
{int w, b;cin >> w >> b;vector<vector<double>> dp(w + 1, vector<double>(b + 1,0));// 定义 dp[i][j] 为 公主 在 i  个白 j 个 黑 的情况下// 获胜的概率for (int j = 1; j <= b; j++)dp[0][j] = 0;for (int i = 1; i <= w; i++)dp[i][0] = 1;for (int i = 1; i <= w; i++){for (int j = 1; j <= b; j++){dp[i][j] += 1.0*i / (i + j);if (j >= 3)dp[i][j] += 1.0*j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) / (i + j - 2) * dp[i][j - 3];if (i >= 1 && j >= 2)dp[i][j] += 1.0*j / (i + j) * (j - 1) / (i + j - 1) * i / (i + j - 2) * dp[i - 1][j - 2];}}cout<<fixed<<setprecision(9)<<dp[w][b]<<"\n";
}
int main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t;t = 1;while (t--){solve();}return 0;
}

添加链接描述
有2^n 支球队比赛,每次和相邻的球队踢,两两淘汰,给定任意两支球队互相踢赢得概率。(2^n 的矩阵,表示两支球队之间踢赢的概率)求最后哪知球队最可能夺冠。

b 站上 一个视频很形象。
在这里插入图片描述

在这里插入图片描述
感觉这道题,就有难点的就是 这个 枚举 i 轮 j 队的对手 队伍。(队伍的编号从 0 开始)
这里使用的神秘的二进制。(啊啊啊,二进制,我是学不会了)
通过一些神秘的观察,大佬发现
枚举K 为队伍的编号
j>>(i-1) ^1 == k>>(i-1),
那么k 可以是 j 队I轮的对手。

#include <bits/stdc++.h>
using namespace std;
int read()
{int x = 0, f = 1;char ch = getchar();while (!isdigit(ch)){if (ch == '-')f = -1;ch = getchar();}while (isdigit(ch)){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}return x * f;
}
void solve()
{int lun;while (cin >> lun && lun != -1){int n = 1<<lun;//这个是 人数 vector<vector<double>> a(n, vector<double>(n));for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cin >> a[i][j];vector<vector<double>> dp(lun + 1, vector<double>(n));for (int i=0;i<n;i++)dp[0][i]=1;for (int i=1;i<=lun;i++){for (int j=0;j<n;j++){for(int k=0;k<n;k++){if(((j>>(i-1)) ^1)  == (k>>(i-1)))dp[i][j]+=dp[i-1][j]*dp[i-1][k]*a[j][k];}}}double mx=-1;int f=-1;for(int i=0;i<n;i++){if (dp[lun][i]>mx){mx=dp[lun][i],f=i;}}cout<<f+1<<"\n"; }}
int main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t;t = 1;// cin>>t;while (t--){solve();}return 0;
}

概率DP求期望(采用逆推)

由终止状态推到起始状态
一般直接将问题作为DP 的状态
luogu
题意:
一个有向无环图,没有重边和自环,起点为1,终点为n。所有点都可以到达终点。
当到达一个顶点,随机走一条边。求从起点走到终点所经过的路径总长度期望是多少。

状态: dp[u]代表点u 到终点n 的路径总长的期望
起点dp[n]=0;
答案是dp[1]
转移:
dp[u]+=(dp[v]+w)/out[u];
直接dfs ,记忆化搜索就可以。
每条边走一遍,每个节点走一遍。所以时间复杂度是
O(n+m)

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;vector<pair<int,double>>e[N];
void solve()
{int n,m;cin>>n>>m;int u,v,w;vector<int>out(n+1);while(m--){cin>>u>>v>>w;e[u].push_back(make_pair(v,w));out[u]++;}vector<double>dp(n+1);dp[n]=0;auto dfs=[&]( auto &&self  ,int u )->void{if (u==n||dp[u]!=0) return; for (int i=0;i<e[u].size();i++){int v=e[u][i].first;int w=e[u][i].second;self(self,v);dp[u]+=(dp[v]+w)/out[u];}};dfs(dfs,1);cout<<fixed<<setprecision(2)<<dp[1]<<"\n";
}
int main()
{int t;t=1;while(t--){solve();}return 0;
}

上面的做法是深搜去做的
我们也可以宽搜去做。
在图中的拓扑排序相当于宽搜。反向建图,使用拓扑排序。

#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
vector<pair<int,double>>e[N];int main()
{int n,m;cin>>n>>m;vector<double>dp(n+1);vector<int>in(n+1);vector<int>t(n+1);int u,v,w;while(m--){cin>>v>>u>>w;e[u].push_back({v,w});in[v]++;t[v]++;}queue<int>q;q.push(n);dp[n]=0;while(!q.empty()){int u=q.front();q.pop();for (int i=0;i<e[u].size();i++){int v=e[u][i].first;int w=e[u][i].second;dp[v]+=(dp[u]+w)/t[v];in[v]--;if (in[v]==0)q.push(v);}}cout<<fixed<<setprecision(2)<<dp[1]<<"\n";return 0;
}

这篇关于概率DP (由一道绿题引起的若干问题。目前为一些老题,蒟蒻的尝试学习1.0)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1146800

相关文章

MySQL 设置AUTO_INCREMENT 无效的问题解决

《MySQL设置AUTO_INCREMENT无效的问题解决》本文主要介绍了MySQL设置AUTO_INCREMENT无效的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参... 目录快速设置mysql的auto_increment参数一、修改 AUTO_INCREMENT 的值。

关于跨域无效的问题及解决(java后端方案)

《关于跨域无效的问题及解决(java后端方案)》:本文主要介绍关于跨域无效的问题及解决(java后端方案),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录通用后端跨域方法1、@CrossOrigin 注解2、springboot2.0 实现WebMvcConfig

Go学习记录之runtime包深入解析

《Go学习记录之runtime包深入解析》Go语言runtime包管理运行时环境,涵盖goroutine调度、内存分配、垃圾回收、类型信息等核心功能,:本文主要介绍Go学习记录之runtime包的... 目录前言:一、runtime包内容学习1、作用:① Goroutine和并发控制:② 垃圾回收:③ 栈和

Go语言中泄漏缓冲区的问题解决

《Go语言中泄漏缓冲区的问题解决》缓冲区是一种常见的数据结构,常被用于在不同的并发单元之间传递数据,然而,若缓冲区使用不当,就可能引发泄漏缓冲区问题,本文就来介绍一下问题的解决,感兴趣的可以了解一下... 目录引言泄漏缓冲区的基本概念代码示例:泄漏缓冲区的产生项目场景:Web 服务器中的请求缓冲场景描述代码

Java死锁问题解决方案及示例详解

《Java死锁问题解决方案及示例详解》死锁是指两个或多个线程因争夺资源而相互等待,导致所有线程都无法继续执行的一种状态,本文给大家详细介绍了Java死锁问题解决方案详解及实践样例,需要的朋友可以参考下... 目录1、简述死锁的四个必要条件:2、死锁示例代码3、如何检测死锁?3.1 使用 jstack3.2

解决JSONField、JsonProperty不生效的问题

《解决JSONField、JsonProperty不生效的问题》:本文主要介绍解决JSONField、JsonProperty不生效的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录jsONField、JsonProperty不生效javascript问题排查总结JSONField

github打不开的问题分析及解决

《github打不开的问题分析及解决》:本文主要介绍github打不开的问题分析及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、找到github.com域名解析的ip地址二、找到github.global.ssl.fastly.net网址解析的ip地址三

MySQL版本问题导致项目无法启动问题的解决方案

《MySQL版本问题导致项目无法启动问题的解决方案》本文记录了一次因MySQL版本不一致导致项目启动失败的经历,详细解析了连接错误的原因,并提供了两种解决方案:调整连接字符串禁用SSL或统一MySQL... 目录本地项目启动报错报错原因:解决方案第一个:第二种:容器启动mysql的坑两种修改时区的方法:本地

springboot加载不到nacos配置中心的配置问题处理

《springboot加载不到nacos配置中心的配置问题处理》:本文主要介绍springboot加载不到nacos配置中心的配置问题处理,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录springboot加载不到nacos配置中心的配置两种可能Spring Boot 版本Nacos

Java中JSON格式反序列化为Map且保证存取顺序一致的问题

《Java中JSON格式反序列化为Map且保证存取顺序一致的问题》:本文主要介绍Java中JSON格式反序列化为Map且保证存取顺序一致的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未... 目录背景问题解决方法总结背景做项目涉及两个微服务之间传数据时,需要提供方将Map类型的数据序列化为co