[BZOJ 3450]Tyvj1952 Easy：期望DP

本文主要是介绍[BZOJ 3450]Tyvj1952 Easy：期望DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

设l为当前期望长度，分为三种情况：

• 当前位为‘x’，l清零
• 当前位为‘o’，ans+=(l+1)^2-l^2，l++
• 当前位为‘?’，那么l可能变成l+1，也可能变成0，因此l的期望变为(l+1)/2，ans+=(2l+1)/2。

/*
User:Small
Language:C++
Problem No.:3450
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
double ans,l;
int n;
char c[300005];
int main(){freopen("data.in","r",stdin);//scanf("%d%s",&n,c);for(int i=0;i<n;i++){if(c[i]=='x') l=0;else if(c[i]=='o') ans+=2*l+1,l++;else ans+=(2*l+1)*0.5,l=(l+1)*0.5;}printf("%.4lf\n",ans);return 0;
}

这篇关于[BZOJ 3450]Tyvj1952 Easy：期望DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---