概率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

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给

Java程序运行时出现乱码问题的排查与解决方法

《Java程序运行时出现乱码问题的排查与解决方法》本文主要介绍了Java程序运行时出现乱码问题的排查与解决方法,包括检查Java源文件编码、检查编译时的编码设置、检查运行时的编码设置、检查命令提示符的... 目录一、检查 Java 源文件编码二、检查编译时的编码设置三、检查运行时的编码设置四、检查命令提示符