[Codeforces-div.1 494C] Helping People

试题分析

不难注意到题目所给的性质是一棵树，所以肯定是树形dp。

那么期望没有办法合并，我们还有一种最笨的方法就是求出概率然后直接乘上权值累加。

然后也不难得出朴素的dp：$f_{i,j}$表示区间$i$，最大值为$mx_i+j$的概率。

也可以很轻松的写出一个$O(nm^2)$的dp，还需优化。

发现转移其中一维是一个前缀和乘积的形式，那么我们改变一下状态：$f_{i,j}$表示区间$i$，最大值$\leq mx_i+j$的概率。

带回式子中检查，它是正确的。

于是$$f[x][j]=p_x\prod f[v][mx_x+j-1-mx_v]+(1-p_x)\prod f[v][mx_x+j-mx_v]$$

#include<iostream>

#include<cstring>

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

#define LL long long

inline int read(){

    int x=0,f=1; char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

    for(;isdigit(c);c=getchar()) x=x*10+c-'0';

    return x*f;

}

const int INF = 2147483600;

const int MAXN = 400010;

const double eps = 1e-6;

struct data{int l,r; double p;}q[MAXN<<1];

int N,Q; int a[MAXN+1],pre[MAXN+1][31],nod;

vector<int> vec[MAXN<<1]; bool vis[MAXN+1];

double f[5001][11051]; int mx;

inline bool cmp(data a,data b){

    if(a.l!=b.l) return a.l<b.l;

    return a.r>b.r;

}

inline void insert(int rt,int l,int r){

    q[++nod].l=l; q[nod].r=r; q[nod].p=0; vec[rt].push_back(nod); return ;

}

inline int build(int rt,int fa,int ql,int qr,int fro){

    if(rt) vec[fa].push_back(rt); vis[rt]=true; int x=-1;

    for(int l=fro,r;l<=Q;l=r){

        if(qr<q[l].r) {x=l; break;}

        r=build(l,rt,q[l].l,q[l].r,l+1);

    } return (x==-1?Q+1:x);

}

int Log2[MAXN+1];

inline int Qt(int l,int r){

    if(l>r) return 0; int x=Log2[r-l+1];

    return max(pre[l][x],pre[r-(1<<x)+1][x]);

}

inline int Query(int x){return Qt(q[x].l,q[x].r);}

inline void dfs(int k,int fa){

    if(vec[k].empty()) {f[k][0]=1.0-q[k].p;

        for(int i=1;i<=Q*2;i++) f[k][i]=1.0; return ;

    } int Mx=Query(k);

    for(int i=0;i<vec[k].size();i++) dfs(vec[k][i],k);

    for(int i=0;i<=Q;i++) {

        double t1,t2; t1=t2=1.0;

        for(int j=0;j<vec[k].size();j++){

            t1=t1*f[vec[k][j]][Mx+i-1-Query(vec[k][j])];

            t2=t2*f[vec[k][j]][Mx+i-Query(vec[k][j])];

        } f[k][i]=(i?q[k].p:0)*t1+(1.0-q[k].p)*t2;

    } for(int i=Q+1;i<=Q*2;i++) f[k][i]=f[k][i-1];

    return ;

}

inline double calc(){

    double ret=mx;

    for(int i=1;i<=Q;i++) ret+=(f[0][i]-f[0][i-1])*i; return ret;

}

int main(){

    //freopen(".in","r",stdin);

    //freopen(".out","w",stdout);

    N=read(),Q=read(); for(int i=1;i<=N;i++) pre[i][0]=a[i]=read(),mx=max(mx,a[i]);

    if(mx>Q) for(int i=1;i<=N;i++) pre[i][0]=a[i]=max(0,a[i]+Q-mx); for(int i=2;i<=N;i++) Log2[i]=Log2[i>>1]+1;

    for(int j=1;j<=21;j++) for(int i=1;i+(1<<j)-1<=N;i++) pre[i][j]=max(pre[i][j-1],pre[i+(1<<(j-1))][j-1]);

    for(int i=1;i<=Q;i++) q[i].l=read(),q[i].r=read(),scanf("%lf",&q[i].p); sort(q+1,q+Q+1,cmp); nod=Q;

    q[0].l=1,q[0].r=N;q[0].p=0; build(0,-1,1,N,1); dfs(0,-1); printf("%.10lf\n",calc());

    return 0;

}

巴特西

[Codeforces-div.1 494C] Helping People

[Codeforces-div.1 494C] Helping People

试题分析

最新文章

热门文章