[BZOJ4318] WJMZBMR打osu! / Easy (期望DP)

题目链接

Solution

Wa,我是真的被期望折服了,感觉这道题拿来练手正好.

DP的难度可做又巧妙...

我们定义:

$f[i]$ 代表到第 $i$ 次点击的时候的最大答案.

$g[i]$ 代表到第 $i$ 此点击的 $o$ 的期望长度.

然后看转移:

1.此时为 $o$ ,那么我可以直接计算答案。

由于 $(x+1)^2=x^2+2x+1$ ,所以我们得到转移方程:

$$f[i]=f[i-1]+2*g[i-1]+1$$

同时由于此时 $o$ 的长度已经增加,所以同时 $g[i]=g[i-1]+1$.

2.此时为 $x$,同样直接统计答案.

$f[i]=f[i-1]$ , $g[i]=0$.

3.此时为 $?$ ,那么我们对于以上两种情况都有 $0.5$ 的概率.

然后直接转移:

$$f[i]=0.5(f[i-1]+2g[i-1]+1+f[i-1])$$

$$g[i]=0.5*(g[i-1]+1)$$

然后最后面 $f[n]$ 即为答案

Code

#include<bits/stdc++.h>

#define db double

using namespace std;

const int maxn=300008;

db f[maxn],g[maxn];

int n;

string ch;

int main()

{

    cin>>n;

    ch='*';

    string s; cin>>s;

    ch+=s;

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

    {

        if(ch[i]=='o')

        {

            f[i]=f[i-1]+2*g[i-1]+1;

            g[i]=g[i-1]+1;

        }

        if(ch[i]=='x')

        {

            f[i]=f[i-1];

            g[i]=0;

        }

        if(ch[i]=='?')

        {

            f[i]=0.5*(f[i-1]+2*g[i-1]+1+f[i-1]);

            g[i]=0.5*(g[i-1]+1);

        }

    }

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

}

巴特西

[BZOJ4318] WJMZBMR打osu! / Easy (期望DP)

题目链接

Solution

Code

最新文章

热门文章