题目描述

有 nnn 个人排成一排，一开始全部面向前方，然后随机朝左或是朝右转。

然后我们不断审查这个队列，每次选择两个面对面的相邻的人，将他们从队列中取出。

例如（> 表示向右，< 表示向左）：

队列 >>><<< 的消除过程为，>>><<< 到 >><< 到 >< 到空队列（每次去除一对）。 队列 >><><<<> 的消除过程为，>><><<<> 到 >><<<> 到 ><<> 到 <>（每次去除一对）。

求最后期望能够剩下多少人。

DP

可以把每个人看做左右括号，那么一对匹配括号会被删除。 设f[i,j]表示做到第i个人还有j个左括号的期望，g[i,j]表示概率，转移很简单。

#include<cstdio> #include<algorithm> #define fo(i,a,b) for(i=a;i<=b;i++) #define fd(i,a,b) for(i=a;i>=b;i--) typedef double db; using namespace std; const int maxn=2000+10; db f[maxn][maxn],g[maxn][maxn],ans; int i,j,k,l,t,n,m; int main(){ scanf("%d",&n); f[0][0]=0; g[0][0]=1; fo(i,0,n-1) fo(j,0,n){ if (j){ f[i+1][j-1]=(f[i+1][j-1]+f[i][j]/2+g[i][j]); g[i+1][j-1]=(g[i+1][j-1]+g[i][j]/2); } else{ f[i+1][j]=(f[i+1][j]+f[i][j]/2); g[i+1][j]=(g[i+1][j]+g[i][j]/2); } f[i+1][j+1]=(f[i+1][j+1]+f[i][j]/2); g[i+1][j+1]=(g[i+1][j+1]+g[i][j]/2); } fo(i,0,n) ans+=f[n][i]; printf("%.3lf",n-ans); }