CF494C Helping People-白红宇

CF494C Helping People

阅读量：6549 次

发布时间：2019-06-24

本文共 1578 字，大约阅读时间需要 5 分钟。

题解

注意到区间之间没有交叉，所以只有包含的关系，我们可以把它整成一棵树。

然后设一下\(dp[i][j]\)表示以\(i\)为根的子树，最大值不超过区间最大值+\(j\)的概率。

转移：

\[ dp[u][j]=p*\prod dp[v][mx[u]-mx[v]-1+j]+(1-p)*\prod dp[v][mx[u]-mx[v]+j] \]

代码

#include
    
     #define N 100002#define M 5002using namespace std;typedef long long ll;int n,nw[N],top,mx[M],q,st[N];vector
     
      vec[N];double f[M][M],ans,g[M][M];int size[M];inline ll rd(){  ll x=0;char c=getchar();bool f=0;  while(!isdigit(c)){if(c=='-')f=1;c=getchar();}  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}  return f?-x:x;}struct node{  int l,r;double p;  inline bool operator <(const node &b)const{    if(l!=b.l)return l
      
       b.r;     }}a[M];void dfs(int u){    int l=a[u].l;    size[u]=u!=0;    for(vector
       
        ::iterator it=vec[u].begin();it!=vec[u].end();++it){        int v=*it;        dfs(v);        for(int i=l;i

::iterator it=vec[u].begin();it!=vec[u].end();++it){ int v=*it; mx[u]=max(mx[u],mx[v]); } for(int i=0;i<=q;++i){ f[u][i]=(1-a[u].p); g[u][i]=a[u].p; } if(now==mx[u])g[u][0]=0; for(vector

::iterator it=vec[u].begin();it!=vec[u].end();++it){ int v=*it; size[u]+=size[v]; for(int j=0;j<=size[u];++j){ if(mx[u]-mx[v]-1+j<=size[u]&&mx[u]-mx[v]-1+j>=0)g[u][j]*=f[v][mx[u]-mx[v]-1+j]; if(mx[u]-mx[v]+j<=size[u])f[u][j]*=f[v][mx[u]-mx[v]+j]; } } for(int i=0;i<=q;++i)f[u][i]+=g[u][i];}int main(){ n=rd();q=rd(); for(int i=1;i<=n;++i)nw[i]=rd(); for(int i=1;i<=q;++i){ a[i].l=rd();a[i].r=rd();scanf("%lf",&a[i].p); } sort(a+1,a+q+1); for(int i=1;i<=q;++i){ while(top&&a[st[top]].r

转载于:https://www.cnblogs.com/ZH-comld/p/11025327.html

你可能感兴趣的文章