CF494C Helping People-蒲公英云

CF494C Helping People

梦里梦外; 2022-01-06 16:07 205阅读 0赞

http://codeforces.com/problemset/problem/494/C

题解

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

然后设一下\(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<bits/stdc++.h> #define N 100002 #define M 5002 using namespace std; typedef long long ll; int n,nw[N],top,mx[M],q,st[N]; vector<int>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.l; else return r>b.r; } }a[M]; void dfs(int u){ int l=a[u].l; size[u]=u!=0; for(vector<int>::iterator it=vec[u].begin();it!=vec[u].end();++it){ int v=*it; dfs(v); for(int i=l;i<a[v].l;++i)mx[u]=max(mx[u],nw[i]); mx[u]=max(mx[u],mx[v]); l=a[v].r+1; } for(int i=l;i<=a[u].r;++i)mx[u]=max(mx[u],nw[i]); int now=mx[u]; for(vector<int>::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<int>::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<a[i].l)top--; vec[st[top]].push_back(i); st[++top]=i; } a[0].l=1;a[0].r=n; dfs(0); for(int i=0;i<=q;++i){ double x=i?f[0][i]-f[0][i-1]:f[0][0]; ans+=x*(mx[0]+i); } printf("%.9lf",ans); return 0; }