云落 wordpress,seo对网店的作用有哪些,wordpress主题演示站点,vps除了做网站还能做什么概率DP#xff1a; 利用动态规划去解决 概率 期望 的题目。
概率DP 求概率#xff08;采用顺推#xff09;
从 初始状态推向结果#xff0c;同一般的DP类似#xff0c;只是经历了概率论知识的包装。 老题#xff1a; 添加链接描述 题意#xff1a; 袋子里有w只白鼠 利用动态规划去解决 概率 期望 的题目。
概率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/ij) 2.先手黑鼠后手白鼠 f[i][j]0 这种情况不用处理 3.先手黑鼠后手黑鼠跑掉白鼠 f[i][j]j/(ij)*(j-1)(ij-1)i(ij-2)dp[i-1][j-2] 4.先手黑鼠后手黑鼠跑黑鼠dp[i][j]j/(ij)(j-1)/(ij-1)(j-2)/(ij-2)*dp[i][j-3];
#include bits/stdc.h
using namespace std;
void solve()
{int w, b;cin w b;vectorvectordouble dp(w 1, vectordouble(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];}}coutfixedsetprecision(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 1lun;//这个是 人数 vectorvectordouble a(n, vectordouble(n));for (int i 0; i n; i)for (int j 0; j n; j)cin a[i][j];vectorvectordouble dp(lun 1, vectordouble(n));for (int i0;in;i)dp[0][i]1;for (int i1;ilun;i){for (int j0;jn;j){for(int k0;kn;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 i0;in;i){if (dp[lun][i]mx){mxdp[lun][i],fi;}}coutf1\n; }}
int main()
{std::cin.tie(nullptr)-sync_with_stdio(false);int t;t 1;// cint;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(nm)
#include bits/stdc.h
using namespace std;
const int N1e55;vectorpairint,doublee[N];
void solve()
{int n,m;cinnm;int u,v,w;vectorintout(n1);while(m--){cinuvw;e[u].push_back(make_pair(v,w));out[u];}vectordoubledp(n1);dp[n]0;auto dfs[]( auto self ,int u )-void{if (un||dp[u]!0) return; for (int i0;ie[u].size();i){int ve[u][i].first;int we[u][i].second;self(self,v);dp[u](dp[v]w)/out[u];}};dfs(dfs,1);coutfixedsetprecision(2)dp[1]\n;
}
int main()
{int t;t1;while(t--){solve();}return 0;
}上面的做法是深搜去做的 我们也可以宽搜去做。 在图中的拓扑排序相当于宽搜。反向建图使用拓扑排序。
#include bits/stdc.h
using namespace std;const int N1e55;
vectorpairint,doublee[N];int main()
{int n,m;cinnm;vectordoubledp(n1);vectorintin(n1);vectorintt(n1);int u,v,w;while(m--){cinvuw;e[u].push_back({v,w});in[v];t[v];}queueintq;q.push(n);dp[n]0;while(!q.empty()){int uq.front();q.pop();for (int i0;ie[u].size();i){int ve[u][i].first;int we[u][i].second;dp[v](dp[u]w)/t[v];in[v]--;if (in[v]0)q.push(v);}}coutfixedsetprecision(2)dp[1]\n;return 0;
}
