宁波江北建设局官方网站,百度推广seo怎么学,wordpress 不显示标题,校园论坛网站建设论文Acwing 218. 扑克牌
题意#xff1a;
一副扑克牌(54张)#xff0c;问得到A 张黑桃、B 张红桃、C 张梅花、D 张方块需要翻开的牌的张数的期望值 E 是多少#xff1f; 如果翻开的牌是大王或者小王#xff0c;Admin 将会把它作为某种花色的牌放入对应堆中#xff0c;使得放…Acwing 218. 扑克牌
题意
一副扑克牌(54张)问得到A 张黑桃、B 张红桃、C 张梅花、D 张方块需要翻开的牌的张数的期望值 E 是多少 如果翻开的牌是大王或者小王Admin 将会把它作为某种花色的牌放入对应堆中使得放入之后 E 的值尽可能小。
题解
事件发生的期望的线性 E(aXbY)aE(X)bE(Y)p(X)×E(X)p(Y)×E(Y)
我们设dp[a][b][c][d][x][y] 已经翻开a~d张花色牌大小王视为x,y花色若x,y0则还没翻开此时还需要期望翻开多少张牌 dp[u] Σp[v] * dp[v]v是u的子状态 转移就是枚举这次翻什么牌这是以恶搞多终点的dag图上dp复杂度为(15 * 4 * 5^2 * 4 ) 代码第33行为什么最后要1 我理解的是这个有点像求图的路径期望长度在本题中每次操作都是翻一张牌从u状态到v状态是通过翻一张牌也可以理解成u到所有v的边权和为1也就是转移方程其实应该是 dp[u] Σ[dp[v] 1 ] * P[v] Σdp[v] * P[v] ΣP[v] Σdp[v] * P[v]1 也可以理解v是u的下一个状态那v怎么都要比u多翻一张牌的期望所有加1
代码
#includebits/stdc.h
#define MAXN 16
using namespace std;
typedef long long ll;const int n 54;
int A,B,C,D;double memo[MAXN][MAXN][MAXN][MAXN][5][5];double dfs(int a, int b, int c, int d, int x, int y){if(memo[a][b][c][d][x][y]) return memo[a][b][c][d][x][y];//到达终状态 if(a(x1)(y1)A b(x2)(y2)B c(x3)(y3)C d(x4)(y4)D) return 0;double sum 54-a-b-c-d-(x!0)-(y!0);double ans 0;if(a 13) ans (13-a)/sum * dfs(a1, b, c, d, x, y);if(b 13) ans (13-b)/sum * dfs(a, b1, c, d, x, y);if(c 13) ans (13-c)/sum * dfs(a, b, c1, d, x, y);if(d 13) ans (13-d)/sum * dfs(a, b, c, d1, x, y);if(x0){double ans1 1e18;for(int i1;i4;i) ans1 min(ans1, 1/sum * dfs(a, b, c, d, i, y));ans ans1;}if(y0){double ans1 1e18;for(int i1;i4;i) ans1 min(ans1, 1/sum * dfs(a, b, c, d, x, i));ans ans1;} return memo[a][b][c][d][x][y] ans 1;
}int main(){cinABCD;int n max(0, A-13) max(0, B-13) max(0, C-13) max(0, D-13);if(n 2){cout-1.000endl;return 0;}printf(%.3f\n, dfs(0,0,0,0,0,0));return 0;
}
