BZOJ3566 SHOI2014概率充电器（动态规划+概率期望）

　　设f[i]为i在子树内不与充电点连通的概率。则f[i]=(1-p_i)·∏(1-q_k+q_k·f[k])。

　　然后从父亲更新答案。则f[i]=f[i]·(1-q_fa+q_fa*f[fa]/(1-q_fa+q_fa*f[i]))。

　　比较好想的dp。注意第二个式子可能会除0。

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } #define N 500010 int n,P[N],p[N],t=0; double f[N],ans=0; struct data{int to,nxt,len; }edge[N<<1]; void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;} void dfs(int k,int from) {f[k]=1-P[k]/100.0;for (int i=p[k];i;i=edge[i].nxt)if (edge[i].to!=from){dfs(edge[i].to,k);f[k]*=(f[edge[i].to]-1)*edge[i].len/100+1;} } void getans(int k,int from) {for (int i=p[k];i;i=edge[i].nxt)if (edge[i].to!=from){double q=edge[i].len/100.0;if (f[edge[i].to]>0) f[edge[i].to]*=1-q+q*f[k]/(1-q+q*f[edge[i].to]);getans(edge[i].to,k);} } int main() { #ifndef ONLINE_JUDGEfreopen("bzoj3566.in","r",stdin);freopen("bzoj3566.out","w",stdout);const char LL[]="%I64d\n"; #elseconst char LL[]="%lld\n"; #endifn=read();for (int i=1;i<n;i++){int x=read(),y=read(),z=read();addedge(x,y,z),addedge(y,x,z);}for (int i=1;i<=n;i++) P[i]=read();dfs(1,1);getans(1,1);for (int i=1;i<=n;i++) ans+=1-f[i];printf("%.6lf",ans);return 0; }

 

转载于:https://www.cnblogs.com/Gloid/p/9709183.html

总结

以上是生活随笔为你收集整理的BZOJ3566 SHOI2014概率充电器（动态规划+概率期望）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。