HGOI 20181027 幻象（概率DP）

• 40 pts: 考场上打了40分暴力，理论的话就是概率树，把每一个状态去去到各个带权（概率）的和就是答案

最终处理的话就是dfs出01序列0代表没有幻象，1代表出现幻象然后在每一次dfs出一段序列的时候双指针check一下更新答案

代码并不难，就是这样写的复杂度O(2)

code： （40pts）

# include <bits/stdc++.h>

using namespace std;

double ans;

int n,a[];

double p1[],p0[];

void get()

{

    double pr=1.0;

    for (int i=;i<=n;i++)

     if (a[i]==) pr*=p1[i];

     else pr*=p0[i];

    int i=; double sum=;

    while (i<=n) {

        if (a[i]==) { i++; continue;}

        int j=i; int res=;

        while (a[j]==&&j<=n) j++,res++;

        i=j;

        sum=sum+(double) res*res;

    }

    ans+=sum*pr;

}

void dfs(int dep)

{

    if (dep==n+) { get(); return; }

    a[dep]=; dfs(dep+);

    a[dep]=; dfs(dep+);

}

int main()

{

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

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

    scanf("%d",&n);

    int x;

    for (int i=;i<=n;i++) {

        scanf("%d",&x);

        p1[i]=(double) x/100.0;

        p0[i]=1.0-p1[i];

    }

    dfs();

    printf("%.1lf\n",ans);

    return ;

}

• 60pts:hjc20032003考场上写了60分DP，这大概是O(n)[前缀积]或者是O(n)复杂度

具体做法是这样的：

令f[i]表示第i秒前幻象的期望，枚举是从j转移过来的，（这里需要注意枚举的j是断点所以从0开始枚举表示不断，否则会重复计数）

转移方程式这样的：

code:(60pts)

# include <bits/stdc++.h>

using namespace std;

const int MAXN=;

double f[MAXN],p[MAXN];

int n;

int main()

{

    scanf("%d",&n); int x;

    for (int i=;i<=n;i++) {

        scanf("%d",&x);

        p[i]=(double)x/100.0;

    }

    f[]=p[];

    for (int i=;i<=n;i++) {

        f[i]=0.0;

        for (int j=;j<=i;j++) {

            double pr=1.0;

            for (int k=j+;k<=i;k++) pr*=p[k];

            f[i]+=pr*(-p[j])*(f[j-]+(i-j)*(i-j));

        }

    }

    printf("%.1lf\n",f[n]);

    return ;

 }

• 100pts: 状态改变一下，

记f[i]为第i秒之前期望幻象值

记g[i]为第i秒前连续期望幻象值

显然

• g[i]=(g[i-1]+1)*P[i]
• f[i]=f[i-1]+P[i]*((g[i-1]+1)-g[i-1])

于是完成了O(1)转移，总复杂度O(n)

code(100 pts)

# include <bits/stdc++.h>

using namespace std;

const int MAXN=1e6+;

double p[MAXN],f[MAXN],g[MAXN];

int n;

double sqr(double x){ return x*x;}

int main()

{

    scanf("%d",&n);

    int x;

    for (int i=;i<=n;i++) {

        scanf("%d",&x);

        p[i]=(double) x/100.0;

    }

    f[]=p[]; g[]=p[];

    for (int i=;i<=n;i++) {

        f[i]=f[i-]+p[i]*(sqr(g[i-]+)-sqr(g[i-]));

        g[i]=(g[i-]+)*p[i];

    }

    printf("%.1lf\n",f[n]);

    return ;

}