令dp[i][0]表示点击i次且第i次失败的期望，dp[i][1]表示点击i次且第i次成功的期望
通过观察分析找规律发现
当i-1次一定失败时dp[i][0]=dp[i-1][0];dp[i][1]=dp[i-1][0]+1;
当i-1次一定成功时dp[i][0]=dp[i-1][1];dp[i][1]=2*dp[i-1][1]+2-dp[i-1][0];
当i-1次一定随机时dp[i][0]=(dp[i-1][0]+dp[i-1][1])/2.0;dp[i][1]=dp[i-1][1]+1.5;
证明……数学推一下？反正我是连推带猜，然后就水过了
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<string> #include<map> #include<algorithm> #include<queue> using namespace std; double dp[300005][2]; int a[300005]; char s[300005]; int n; int main() { int i,j,k,l; scanf("%d",&n); scanf("%s",s+1); for(i=1;i<=n;i++){ if(s[i]=='x')a[i]=0; if(s[i]=='o')a[i]=1; if(s[i]=='?')a[i]=2; } dp[1][0]=0; dp[1][1]=1; for(i=2;i<=n;i++){ if(a[i-1]==0){ dp[i][0]=dp[i-1][0]; dp[i][1]=dp[i-1][0]+1; } if(a[i-1]==1){ dp[i][0]=dp[i-1][1]; dp[i][1]=2*dp[i-1][1]+2-dp[i-1][0]; } if(a[i-1]==2){ dp[i][0]=(dp[i-1][0]+dp[i-1][1])/2.0; dp[i][1]=dp[i-1][1]+1.5; } } if(a[n]==0)printf("%.4lf",dp[n][0]); if(a[n]==1)printf("%.4lf",dp[n][1]); if(a[n]==2)printf("%.4lf",(dp[n][0]+dp[n][1])/2.0); return 0; }