【概率DP】CF494C Helping People

【题目】
CF
有一个长度为$n$的数列$a$，有$m$个操作，每个操作有 p i p_i pi​的概率给 [ l i , r i ] [l_i,r_i] [li​,ri​]加一，所有操作的区间仅有完全包含和不相交关系。求所有操作后$a$中最大值的期望。
n ≤ 1 0 5 , m ≤ 5000 n\leq 10^5,m\leq 5000 n≤105,m≤5000

【解题思路】
题目给出的限制实际上是一棵树结构，完全包含的区间外层为父亲，内层为儿子。

观察到操作数比较少，也就是说最后加的权值比较小，考虑针对这个东西来$\text{DP}$。

不妨令 f i , j f_{i,j} fi,j​表示$i$子树操作结束后，$i$点代表的区间最大值 ≤ m x i + j \leq mx_i+j ≤mxi​+j的概率，其中 m x i mx_i mxi​表示原区间最大值。那么若当前操作不执行，只需要所有子树中最大值均 ≤ m x i + j \leq mx_i+j ≤mxi​+j的概率和。否则需要所有子树中最大值均 ≤ m x i + j − 1 \leq mx_i+j-1 ≤mxi​+j−1的概率和，那么可以得到：

f i , j = p i ∏ f v , m x i + j − 1 − m x v + ( 1 − p i ) ∏ f v , m x i + j − m x v f_{i,j}=p_i\prod f_{v,mx_i+j-1-mx_v}+(1-p_i)\prod f_{v,mx_i+j-mx_v} fi,j​=pi​∏fv,mxi​+j−1−mxv​​+(1−pi​)∏fv,mxi​+j−mxv​​

复杂度 O ( n log ⁡ n + m 2 ) O(n\log n+m^2) O(nlogn+m2)
【参考代码】

#include
#define pb push_back
using namespace std;typedef double db;
const int N=1e5+10,M=5010;
int n,m,Log[N],fc[20],st[18][N];
db f[M][M];
vector<int>G[M];struct data
{int l,r,mx;db p;data(int _l=0,int _r=0,int _m=0,db _p=0):l(_l),r(_r),mx(_m),p(_p){}
}q[M];
bool cmp(const data&A,const data&B){return A.l==B.l?A.r>B.r:A.l<B.l;}void dfs(int x)
{db p=1;for(auto v:G[x]) dfs(v);for(auto v:G[x]) p*=f[v][q[x].mx-q[v].mx];f[x][0]=(1-q[x].p)*p;for(int i=1;i<=m;++i){db p1=1,p2=1;for(auto v:G[x]) p1*=f[v][min(q[x].mx+i-q[v].mx-1,m)],p2*=f[v][min(q[x].mx+i-q[v].mx,m)];f[x][i]=q[x].p*p1+(1-q[x].p)*p2;}
}int query(int l,int r)
{int k=Log[r-l+1];return max(st[k][l],st[k][r-fc[k]+1]);
}int main()
{
#ifdef Durant_Leefreopen("CF494C.in","r",stdin);freopen("CF494C.out","w",stdout);
#endifscanf("%d%d",&n,&m);for(int i=1;i<=n;++i) scanf("%d",&st[0][i]);fc[0]=1;for(int i=1;i<20;++i) fc[i]=fc[i-1]<<1;for(int i=2;i<=n;++i) Log[i]=Log[i>>1]+1;for(int j=1;j<17;++j) for(int i=1;i+fc[j]-1<=n;++i)st[j][i]=max(st[j-1][i],st[j-1][i+fc[j-1]]);for(int i=1;i<=m;++i){scanf("%d%d%lf",&q[i].l,&q[i].r,&q[i].p);q[i].mx=query(q[i].l,q[i].r);}q[++m]=data(1,n,query(1,n),0);sort(q+1,q+m+1,cmp);for(int i=2;i<=m;++i) for(int j=i-1;j;--j) if(q[j].l<=q[i].l && q[i].r<=q[j].r) {G[j].pb(i);break;}dfs(1);db ans=f[1][0]*q[1].mx;for(int i=1;i<=m;++i) ans+=(f[1][i]-f[1][i-1])*(q[1].mx+i);printf("%lf\n",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！