题解 P6036 【Ryoku 爱学习】

· · 题解

推荐在博客查看

补篇题解QAQ

当初比赛时真的羞涩, 看到公式就已经傻了, 不敢想。。

其实挺简单一题，大力推公式上dp过了那种

各路神仙做题前可以顺便切下这道P1654 OSU!有些帮助。

期望dp

说白了就是用期望的形式写式子, 然后dp递推一下QAQ（

由期望的线性可加, 我们珂以对题中所说的每个连续掌握时刻求和

也就是:

Ans=\sum_{1\le l \le r \le n}a^{b(r-l)}(1-p_{l-1})(1-p_{r+1})\prod{p_{l\dots r}}\sum{w_{l\dots r}}

稍加整理:

Ans=\sum_{r=1}^{n}(1-p_{r+1})\sum_{l=1}^{r}a^{b(r-l)}(1-p_{l-1})\prod{p_{l\dots r}}\sum{w_{l\dots r}}

我们把后面一堆设掉:

f_i=\sum_{l=1}^{i}a^{b(i-l)}(1-p_{l-1})\prod{p_{l\dots i}}\sum{w_{l\dots i}}

这样Ans=\sum(1-p_{i+1})f_i

把w_i和它的系数提出, 发现其他的项和f_{i-1}有关, 得到:

f_i=f_{i-1}\ a^b\ p_i+w_{i}\ \sum_{l=1}^{i}a^{b(i-l)}(1-p_{l-1})\prod{p_{l\dots i}}

后面的再设一个:

t_i=\sum_{l=1}^{i}a^{b(i-l)}(1-p_{l-1})\prod{p_{l\dots i}}

式子和f很像, 而且一样可以递推...

这样f_i=f_{i-1}\ a^b\ p_i+w_{i}\ t_i

写t_i怎么递推:

t_i=t_{i-1}\ a^b\ p_i+p_i(1-p_{i-1})

大功告成！

The code time：

// Etavioxy
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<cmath>
#define il inline
#define ll long long
#define rep(i,s,t) for(register int i=(s);i<=(t);i++)
#define rev_rep(i,s,t) for(register int i=(s);i>=(t);i--)
#define each(i,u) for(int i=head[u];i;i=bow[i].nxt)
#define file(s) freopen(s".in" ,"r",stdin),freopen(s".out","w",stdout)
#define pt(x) putchar(x)
using namespace std;
il int ci(){
    register char ch;int f=1;
    while(!isdigit(ch=getchar()))f=ch=='-'?-1:1;
    register int x=ch^'0';
    while(isdigit(ch=getchar()))x=(x*10)+(ch^'0');
    return f*x;
}

enum{N=100023};

double f[N],t[N],p[N];
int w[N];

int main(){
    int n=ci(); double a,b;
    scanf("%lf%lf",&a,&b);
    double x=pow(a,b);
    rep(i,1,n) w[i]=ci();
    rep(i,1,n) scanf("%lf",&p[i]);
    double ans = 0;
    rep(i,1,n){
        t[i] = x*p[i]*t[i-1]+p[i]*(1-p[i-1]);
        f[i] = x*p[i]*f[i-1]+t[i]*w[i];
        ans += (1-p[i+1])*f[i];
    }
    printf("%lf\n",ans);
    return 0;
}

虽然所有的推导都不够灵性。但是乱用公式却意外地好理解qwq。嗯嗯谔谔nya nya nya ~

确定不是您看错了? (公式没问题的啊