題目描述
n次向一個棧中加入0或1中隨機1個，如果一次加入0時棧頂元素為1，則將這兩個元素彈棧。問最終棧中元素個數的期望是多少。
輸入
一行一個正整數 n 。
輸出
一行一個實數，表示期望剩下的人數，四舍五入保留三位小數。
樣例輸入
10
樣例輸出
4.168
題解
概率期望dp
顯然任何時刻棧中的元素自底至頂一定是若干個0+若干個1。
但是如果設狀態$p[i][j][k]$表示前$i$次操作，棧中$j$個0，$k$個1的概率，復雜度是$O(n^3)$的，顯然會TLE。
注意到$0$的個數對狀態轉移是沒有影響的，而期望在任何時刻都具有可加性，因此可以設$f[i][j]$表示前$i$次操作，棧中$j$個1的期望元素個數。
那么直接考慮新加入一個是0還是1，看一下長度是增加還是減少即可。
這里有一個問題：每次增加或減少的長度是多少？由于我們設的是總情況的期望，而期望等于 概率*權值 ，這種情況的權值為1，因此期望值就是這種情況的概率。
所以還需要維護一個$p[i][j]$表示前$i$次操作，棧中$j$個1的概率。每次使用概率轉移期望即可。
時間復雜度$O(n^2)$
#include <cstdio>
#define N 2010
double p[N][N] , f[N][N];
int main()
{int n , i , j;double ans = 0;scanf("%d" , &n) , p[0][0] = 1;for(i = 0 ; i < n ; i ++ ){p[i + 1][1] += p[i][0] / 2 , f[i + 1][1] += (f[i][0] + p[i][0]) / 2;p[i + 1][0] += p[i][0] / 2 , f[i + 1][0] += (f[i][0] + p[i][0]) / 2;for(j = 1 ; j < n ; j ++ ){p[i + 1][j + 1] += p[i][j] / 2 , f[i + 1][j + 1] += (f[i][j] + p[i][j]) / 2;p[i + 1][j - 1] += p[i][j] / 2 , f[i + 1][j - 1] += (f[i][j] - p[i][j]) / 2;}}for(i = 0 ; i <= n ; i ++ ) ans += f[n][i];printf("%.3lf\n" , ans);return 0;
}
?
和==)
