n次向一个栈中加入0或1中随机1个，如果一次加入0时栈顶元素为1，则将这两个元素弹栈。问最终栈中元素个数的期望是多少。
首先容易想到用概率算期望，p[i][j][k]表示已加入i个数，1有j个，总长为k的概率。（显然栈中一定是先一些0再是1）。
考虑优化，容易想到f[i][j]表示已加入i个数，1有j个时，栈中的期望元素个数。
讨论下一个放入的数是0还是1，直接转移即可。
每次转移是状态是f[i]=(f[k]+1)*p[k][i]，其中k是能到达i的所有状态，p[k][i]是i由k转移到的概率（注意不是k转移到i的概率）。
同时维护P和f即可，注意j=0时要特判。
1 #include2 #include 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 4 using namespace std; 5 6 const int N=2010; 7 const double eps=1e-12; 8 int n; 9 double ans,p[N][N],f[N][N];10 double Abs(double x){ return (x<0) ? -x : x; }11 12 int main(){13 scanf("%d",&n); p[0][0]=1;14 rep(i,0,n-1){15 p[i+1][1]+=p[i][0]/2; p[i+1][0]+=p[i][0]/2;16 rep(j,1,n-1) p[i+1][j+1]+=p[i][j]/2,p[i+1][j-1]+=p[i][j]/2;17 if (p[i+1][1]>eps) f[i+1][1]+=(f[i][0]+1)*p[i][0]/(2*p[i+1][1]);18 if (p[i+1][0]>eps) f[i+1][0]+=(f[i][0]+1)*p[i][0]/(2*p[i+1][0]);19 rep(j,1,n-1)20 f[i+1][j+1]+=(f[i][j]+1)*((Abs(p[i+1][j+1])