Sticker Album

Sticker Album

期望DP裸题,选取(现有卡数,还需抽卡期望)为状态。
期望DP最重要的方程是,从结果向前推,利用全概率公式:
E = ∑ i p i ∗ ( E i + c o s t i ) E=\sum_i p_i*(E_i+cost_i) E=∑i​pi​∗(Ei​+costi​)
在此问题中,已知后一步期望,则+1为转移过去的cost,乘p即可。

那么若不考虑取出0张,转移方程如下:
f i = ( ∑ j = a b ( f i + j + 1 ) ) / ( b − a + 1 ) f_i=(\sum_{j=a}^b (f_{i+j}+1))/(b-a+1) fi​=(∑j=ab​(fi+j​+1))/(b−a+1)
对于a=0有
f i = ( ( ∑ j = a + 1 b ( f i + j + 1 ) ) + f i + 1 / ( b − a + 1 ) f_i=((\sum_{j=a+1}^b (f_{i+j}+1))+f_i+1/(b-a+1) fi​=((∑j=a+1b​(fi+j​+1))+fi​+1/(b−a+1)
化为:
f i = ( ( ∑ j = a + 1 b ( f i + j + 1 ) ) + 1 / ( b − a ) f_i=((\sum_{j=a+1}^b (f_{i+j}+1))+1/(b-a) fi​=((∑j=a+1b​(fi+j​+1))+1/(b−a)
那么从n-1向0DP即可,但是每个方程中都有一个序列求和,这个复杂度不能接受。注意到,这些和在处理 f i f_i fi​时都已确定,不会再变,所以可以做一个后缀和,每次求出f更新之。

int n,a,b;cin>>n>>a>>b;
for(int i=n-1;i>=0;--i){
    double tmp=0;
    if(a==0){
        tmp=sum[i+a+1]-sum[i+b+1];
        f[i]=(tmp+b-a+1)/(b-a);
    }else{
        tmp=sum[i+a]-sum[i+b+1];
        f[i]=(tmp)/(b-a+1)+1;
    }
    sum[i]=sum[i+1]+f[i];
}
printf("%.6lf",f[0]);
上一篇:在PostgreSQL中使用oracle_fdw访问Oracle


下一篇:php – 通过SSL的Laravel Redis缓存?