首先一点特别难想到的就是,如何跑到树上去。良心的题目规定了区间不交错,这使得我们对于每一个区间看成一个节点,那么这个节点的子节点就是这个区间的子区间,这样子建好树后,考虑概率 $\rm{DP}$ 。

当然我们需要规定更节点为 $1,n$ ,这样方便统计答案。

设 $f_{i,j}$ 表示 $i$ 节点所代表的区间的最大值不大于 $j+mx_i$ 的概率(其中 $mx_i$ 表示 $i$ 代表的区间在原数列中的最大值),转移枚举每一个儿子即可:

$$f_{u,j}=f1\prod_{v\in son_u}f_{v,\min(q+1,j+mx_u-mx_v-1)}+f2\prod_{v\in son_u}f_{v,\min(q+1,j+mx_u-mx_v)}$$

其中 $f1$ 表示 $i$ 被触发的概率,$f2$ 表示 $i$ 没有被触发的概率。

然后就是统计答案,对于数值为 $j$ 的答案应该为 $f_{1,j}-f_{1,j-1}$ 了,算一下期望就好了。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=1e5+2;
const int Q=5e3+8;

int n,q,a[N],head[Q],cnt;
struct Edge {int nxt,to;} G[Q<<1];
struct node {
    int l,r,mx;double p;
    bool friend operator <(node a,node b){return a.l==b.l?a.r>b.r:a.l<b.l;}
}Int[Q];

void add(int u,int v) {G[++cnt]=(Edge){head[u],v},head[u]=cnt;}

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

struct Segment_tree {
    #define mid ((l+r)>>1)
    int val[N<<4];
    void build(int x,int l,int r) {
        if(l^r) build(x<<1,l,mid),build(x<<1|1,mid+1,r),val[x]=max(val[x<<1],val[x<<1|1]);
        else scanf("%d\n",val+x);
    }
    int query(int x,int l,int r,int L,int R) {
        if(L==l&&r==R) return val[x];
        if(R<=mid) return query(x<<1,l,mid,L,R);
        else if(L>mid) return query(x<<1|1,mid+1,r,L,R);
        else return max(query(x<<1,l,mid,L,mid),query(x<<1|1,mid+1,r,mid+1,R));
    }
}T;

int dep[Q];
double dp[Q][Q];
void dfs(int u) {
    dep[u]=1;
    for(int i=head[u];i;i=G[i].nxt)
        dfs(G[i].to),dep[u]=max(dep[u],dep[G[i].to]+1);
    for(int j=0;j<=dep[u];++j) {
        double f1=j?Int[u].p:0,f2=1-Int[u].p;
        for(int i=head[u];i;i=G[i].nxt) {
            int v=G[i].to;
            if(j+Int[u].mx-Int[v].mx-1>=0) f1*=dp[v][min(q+1,j+Int[u].mx-Int[v].mx-1)];
            f2*=dp[v][min(q+1,j+Int[u].mx-Int[v].mx)];
        }dp[u][j]=f1+f2;
    }
    for(int j=dep[u]+1;j<=q+1;++j) dp[u][j]=1;
}

int main() {
    IN(n),IN(q);
    T.build(1,1,n);
    for(int i=1;i<=q;++i)
        scanf("%d%d%lf",&Int[i].l,&Int[i].r,&Int[i].p),
        Int[i].mx=T.query(1,1,n,Int[i].l,Int[i].r);
    Int[++q]=(node){1,n,T.val[1],0};
    sort(Int+1,Int+1+q);
    for(int i=2;i<=q;++i)
        for(int j=i-1;j;--j)
            if(Int[j].l<=Int[i].l&&Int[i].r<=Int[j].r) {add(j,i);break;}
    dfs(1);
    double mx=Int[1].mx,ans=dp[1][0]*mx;
    for(int i=1;i<=dep[1];++i)
        ans+=(dp[1][i]-dp[1][i-1])*(mx+i);
    printf("%.6lf\n",ans);
    return 0;
}
最后修改:2019 年 05 月 30 日 03 : 26 PM