首页 > 代码库 > 【BZOJ】3450 Tyvj1952 Easy

【BZOJ】3450 Tyvj1952 Easy

【算法】期望DP

【题解】http://blog.csdn.net/vmurder/article/details/46471319

注意期望先算,长度后加,就可以避免一些负数问题。

期望长度的计算没有问题,期望其实可以看作就是一个实际的数、已知的数。

技术分享
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
double l,ans;
char s[300010];
int main()
{
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;i++)
     {
         if(s[i]==x)l=0;
         if(s[i]==o)ans+=l*2+1,l++;
         if(s[i]==?)ans+=l+0.5,l=(l+1)/2;
     }
    printf("%.4lf",ans);
    return 0;
}
View Code

 

【BZOJ】3450 Tyvj1952 Easy