正文 

当前位置： 首页 > java > java教程

bzoj3566概率充电器（动态规划）

小蒟蒻yyb的博客 小蒟蒻yyb的博客     2022-10-28     549

关键词：

【BZOJ3566】概率充电器（动态规划）

题面

BZOJ

Description

著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品——概率充电器:
“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!
”
SHOI 概率充电器由 n-1 条导线连通了 n 个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率决定。
随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。
作为 SHOI 公司的忠实客户,你无法抑制自己购买 SHOI 产品的冲动。在排了一个星期的长队之后终于入手了最新型号的 SHOI 概率充电器。
你迫不及待地将 SHOI 概率充电器插入电源——这时你突然想知道,进入充电状态的元件个数的期望是多少呢?

Input

第一行一个整数:n。概率充电器的充电元件个数。充电元件由 1-n 编号。
之后的 n-1 行每行三个整数 a, b, p,描述了一根导线连接了编号为 a 和 b 的
充电元件,通电概率为 p%。
第 n+2 行 n 个整数:qi。表示 i 号元件直接充电的概率为 qi%。

Output

输出一行一个实数,为进入充电状态的元件个数的期望,四舍五入到六位小数

Sample Input

3

1 2 50

1 3 50

50 0 0

Sample Output

1.000000

HINT

对于 100%的数据,n≤500000,0≤p,qi≤100。

题解

很明显要求出所有点的通电的概率，直接相加即可
但是这个概率不好算，我们反过来，求每个点不通电的概率。

设\(f[i]\)表示\(i\)不通电的概率
\(f[u]=(1-q[u])*\prod_v(f[v]+(1-f[v])*(1-p[u,v]))\)
但是这样子少考虑了父亲的影响
于是再做一遍\(dp\)，考虑父亲节点的影响就行了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 555555
inline int read()

    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;

struct Lineint v,next;double w;e[MAX<<1];
int h[MAX],cnt=1,n;
inline void Add(int u,int v,double w)e[cnt]=(Line)v,h[u],w;h[u]=cnt++;
double f[MAX],g[MAX],q[MAX],pf[MAX];
void dfs(int u,int ff)

    f[u]=1.0-q[u];int tt=0;
    for(int i=h[u];i;i=e[i].next)
    
        int v=e[i].v;
        if(v==ff)continue;
        pf[v]=e[i].w;dfs(v,u);
        double P=f[v]+(1-f[v])*(1-e[i].w);
        if(P>0)f[u]=f[u]*P;
        else ++tt;
    
    for(int i=h[u];i;i=e[i].next)
    
        int v=e[i].v;
        if(v==ff)continue;
        double P=f[v]+(1-f[v])*(1-e[i].w);
        if(P>0)if(!tt)g[v]=f[u]/P;
        else if(tt==1)g[v]=f[u];
    
    if(tt)f[u]=0;

void DFS(int u,int ff)

    if(ff)
        g[u]=g[u]*(g[ff]+(1-g[ff])*(1-pf[ff]));
    for(int i=h[u];i;i=e[i].next)
        if(e[i].v!=ff)DFS(e[i].v,u);

int main()

    n=read();
    for(int i=1;i<n;++i)
    
        int u=read(),v=read(),p=read();
        Add(u,v,0.01*p);Add(v,u,0.01*p);
    
    for(int i=1;i<=n;++i)q[i]=0.01*read();
    dfs(1,0);DFS(1,0);
    for(int i=1;i<=n;++i)f[i]=f[i]*(g[i]+(1-g[i])*(1-pf[i]));
    double ans=0;
    for(int i=1;i<=n;++i)ans+=1.0-f[i];
    printf("%.6lf\n",ans);
    return 0;

bzoj3566概率充电器概率dp

哼我就要正着推链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3566 题意：节点有没有电看脸，线好不好看脸，问一个正常的亚洲人会给几个东西充上电。我就正着推了怎么地首先，我们定义一下数组含义，$f[x]$表示这个点有电... 查看详情

●bzoj3566[shoi2014]概率充电器

题链：http://www.lydsy.com/JudgeOnline/problem.php?id=3566题解：概率dp，树形dp 如果求出每个点被通电的概率t， 那么期望答案就是t1×1+t2×1+t3*1+...+tn×1 现在问题就是要去求每个点被通电的概率。 因为是一颗树，所以每个点是否... 查看详情

bzoj3566:[shoi2014]概率充电器

...SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”SHOI概率充电器由n-... 查看详情

bzoj3566[shoi2014]概率充电器

...刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数 查看详情

bzoj3566[shoi2014]概率充电器树形概率dp

...刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”SHOI概率充... 查看详情

bzoj3566

3566:[SHOI2014]概率充电器TimeLimit: 40Sec  MemoryLimit: 256MBSubmit: 982  Solved: 422[Submit][Status][Discuss]Description著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全 查看详情

bzoj3566:[shoi2014]概率充电器树形概率dp(代码片段)

设g[u]为这个点被儿子和自己充上电的概率，f[u]为被儿子、父亲和自己充上电的概率然后根据贝叶斯公式（好像是叫这个），1.P(A+B)=P(A)+P(B)-P(A)*P(B)，2.P(A)=(P(A+B)-P(B))/(1-P(B))g的转移很好想，根据上面的1公式，g[u]=g[u]+g[e[i].to]*e[i].p-g... 查看详情

[bzoj3566][shoi2014]概率充电器(代码片段)

传送门DescriptionSHOI概率充电器由n-1条导线连通了n个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率决定。随后电能可以从直接充电的元件经过通电的导线使得其他充电元... 查看详情

题解亚瑟王hnoi2015bzoj4008概率期望动态规划

...：http://www.lydsy.com/JudgeOnline/problem.php?id=4008一道不简单的概率和期望dp题根据期望的线性性质，容易想到，可以算出每张卡的期望伤害，然后全部加在一起手算样例之后发现是正确的，那么我们只要求出每张卡的实际被使用的概率... 查看详情

bzoj1419redisgood-动态规划-概率与期望

Description桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1美元，黑牌则付出1美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。Input一行输入两个数R,B,其值在0到5000之间Outp... 查看详情

bzoj4008亚瑟王-动态规划-概率与期望

...众所周知，亚瑟王是一个看脸的游戏，技能的发动都是看概率的。作为一个非洲人，同时作为一个前OIer，小K自然是希望最大化造成伤害的期望值。但他已经多年没写过代码，连Spaly都敲不对了，因此，希望你能帮帮小K，让他感... 查看详情

bzoj2134单位错选（数学期望，动态规划）

【BZOJ2134】单位错选（数学期望，动态规划）题面BZOJ题解单独考虑相邻的两道题目的概率就好了没了呀。。#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>#includ 查看详情

概率期望动态规划

虽然概率DP有许多数学期望的知识，但是终究无法偏离动态规划的主题。动态规划该有的特点继续保留，另外增添了一些概率期望的神秘色彩。 [1]机器人·述题意：    多组输入n,m,l,r。表示在一个环上有n个格子... 查看详情

bzoj2998problema（动态规划）

【BZOJ2998】ProblemA（动态规划）题面BZOJ题解一个人的成绩范围可以确定为一个区间这样就变成了选择若干区间，不重合，每个区间有个权值，求最大权值和这样就可直接\(dp\)了#include<iostream>#include<cstdio>#include<cstdlib>#... 查看详情

bzoj3992序列统计（动态规划，ntt）

【BZOJ3992】序列统计（动态规划，NTT）题面BZOJ题解最裸的暴力设(f[i][j])表示前(i)个数，积在膜意义下是(j)的方案数转移的话，每次枚举一个数，直接丢进去就好复杂度(O(nm|S|))，10pts#include<iostream>#include<cstdio>#include<cstdl... 查看详情

bzoj1899午餐（动态规划）

【BZOJ1899】午餐（动态规划）题面BZOJ题解我太弱了这种(dp)完全做不动。。首先，感性理解一些如果所有人都要早点走，那么，吃饭时间长的就先吃吃饭时间短的就晚点吃所以，按照吃饭时间排序我们不难得出一个每个人吃完饭... 查看详情

bzoj2037sue的小球（动态规划）

【BZOJ2037】Sue的小球（动态规划）题面BZOJ题解莫名想到这道题目很明显是一样的设(f[i][j][0/1])表示已经接到了(i～j)这一段的小球当前在(i)或者在(j)的最小费用这个费用是随着时间增长，没有被接到的小球产生的这样就可以避免存... 查看详情

bzoj2442修建草坪（动态规划，单调队列）

【BZOJ2442】修建草坪（动态规划，单调队列）题面权限题。。洛谷题解设(f[i])表示前(i)个里面选出来的最大值转移应该比较显然枚举一个断点的位置，转移一下就好(f[i]=max(f[j-1]+s[j]-s[i]))所以可以单调队列优化一下(不优化用各种... 查看详情