CF494C Helping People
题意翻译
有一个长为 (n) 的数列，初始时为 (a_{1dots n})。
给你 (q) 个操作，第 (i) 个操作将 ([l_i,r_i]) 内的数全部加一，有 (p_i) 的概率被执行。保证区间不会交错，即：(forall i,jin[1,q],l_ile r_i<l_jle r_j) 或 (l_ile l_jle r_jle r_i) 或 (l_jle r_j<l_ile r_i) 或 (l_jle l_ile r_ile r_j) 。
求操作完成后数列的最大值的期望。
输入格式
第一行 (n,\,q\,(1le nle10^5,\,1le qle 5000))。
第二行 (a_1,\,a_2,\,cdots,\,a_n\,(0le a_ile10^9))。
接下来 (q) 行，每行 (l_i,\,r_i,\,p_i\,(1le l_ile r_ile n,\,0le p_ile1))。
输出格式
一个实数，表示答案，绝对/相对误差在 (10^{-6})内算对。
Translated by ouuan.
考虑区间不交错的用处，一个区间向ta完全包含的区间连边，可以构成一棵树。
然后区间又只有5000个，搞一个(n^2)的树形dp多好
考虑求出每个最大值的概率。
令(dp_{i,j})代表区间(i)最大值不大于(j+max_{lle ile r}a_i)的概率，这样等于的概率只需要(dp_{i,j}-dp_{i,j-1})就可以得到了
转移
[dp_{i,j}=p_iprod_sdp_{s,j+max_i-max_v-1}+(1-p_i)prod_sdp_{s,j+max_i-max_v}
]
注意上下边界。
Code:
#include <cstdio>
#include <algorithm>
#define ls id<<1
#define rs id<<1|1
using std::max;
using std::min;
const int N=5010;
int head[N],to[N<<1],Next[N<<1],cnt;
void add(int u,int v)
{
to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;
}
int n,q;
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;}
}s[N];
int mx[N*80];
void build(int id,int l,int r)
{
int mid=l+r>>1;
if(l^r) build(ls,l,mid),build(rs,mid+1,r),mx[id]=max(mx[ls],mx[rs]);
else scanf("%d",mx+id);
}
int query(int id,int L,int R,int l,int r)
{
if(l==L&&r==R) return mx[id];
int Mid=L+R>>1;
if(r<=Mid) return query(ls,L,Mid,l,r);
else if(l>Mid) return query(rs,Mid+1,R,l,r);
else return max(query(ls,L,Mid,l,Mid),query(rs,Mid+1,R,Mid+1,r));
}
int dep[N];
double dp[N][N];
void dfs(int now)
{
dep[now]=1;
for(int i=head[now];i;i=Next[i]) dfs(to[i]),dep[now]=max(dep[now],dep[to[i]]+1);
for(int j=0;j<=dep[now];j++)
{
double f1=j?s[now].p:0,f2=1-s[now].p;
for(int i=head[now];i;i=Next[i])
{
int v=to[i];
if(j+s[now].mx-s[v].mx-1>=0) f1*=dp[v][min(q+1,j+s[now].mx-s[v].mx-1)];
f2*=dp[v][min(q+1,j+s[now].mx-s[v].mx)];
}
dp[now][j]=f1+f2;
}
for(int i=dep[now]+1;i<=q+1;i++) dp[now][i]=1;
}
int main()
{
scanf("%d%d",&n,&q);
build(1,1,n);
for(int i=1;i<=q;i++)
{
scanf("%d%d%lf",&s[i].l,&s[i].r,&s[i].p);
s[i].mx=query(1,1,n,s[i].l,s[i].r);
}
s[++q]={1,n,mx[1],0};
std::sort(s+1,s+1+q);
for(int i=2;i<=q;i++)
for(int j=i-1;j;j--)
if(s[j].l<=s[i].l&&s[i].r<=s[j].r)
{
add(j,i);
break;
}
dfs(1);
double x=s[1].mx,ans=dp[1][0]*x;
for(int i=1;i<=dep[1];i++)
ans+=(dp[1][i]-dp[1][i-1])*(x+i);
printf("%.6lf
",ans);
return 0;
}
2019.1.13