?題目鏈接：Problem - D - Codeforces
看了這篇文章來的：【算法學習筆記】概率與期望DP - RioTian - 博客園
這篇博客寫得挺好的，講了一些常見方法，概率 / 期望的題多練練就上手了。
題目大意：
n 個人排隊上電梯，每次只有隊首那個人可能上電梯，且他上電梯的概率為 p ，一旦上去就不會下來，求 t 秒之后電梯上的人數的期望。
Solution1:
利用期望的定義計算，即 期望 = sum(概率 * 權重) 。
設??表示?i 秒之后電梯上有 j 個人的概率，那么?
下面考慮轉移方程：
顯然?
假設當前狀態是??，如果此時 j == n 了，那么轉移直接就是?
(這一步特判必不可少，因為要滿足全概率為 1 的穩定性)
如果 j < n ，則轉移取決于此時隊首這個人上不上電梯：
上：
不上：
Code:
#include<cstdio>
#include<cstring>
using namespace std;#define N 2005int n,t;
double p,f[N][N],ans;int main()
{scanf("%d%lf%d",&n,&p,&t);f[0][0] = 1.00,ans = 0.00;for (int i = 0;i < t;++ i){f[i + 1][n] = f[i][n];for (int j = 0;j < n;++ j)f[i + 1][j] += f[i][j] * (1 - p),f[i + 1][j + 1] += f[i][j] * p;}for (int i = 1;i <= n;++ i)ans += i * f[t][i];printf("%.6lf\n",ans);return 0;
}Solution2:
另一種比較巧妙的技巧，就是把狀態抽象成點，把狀態之間的轉移抽象成邊。
定義：只有從狀態 (i,j) 轉移到 (i + 1,j + 1) 的邊的邊權為1，從狀態 (i,j) 轉移到 (i + 1,j) 的邊的邊權設置為 0 ，那么這里邊權的意義就是此次轉移增加了電梯上的幾個人（1或0）。于是問題轉化成了計算每條邊的期望通過次數。
設想一下，如果我們知道通過每個 "點" 的期望次數，那 "邊" 不就迎刃而解了嗎？于是問題又轉化成了計算每個點的期望通過次數。
設??表示通過狀態 (i,j) 這個點的期望次數，那么有：
可以發現其實和 Solution1 如出一轍。
那么對于 "從狀態 (i,j) 轉移到 (i + 1,j + 1) 的邊" 的期望通過次數就是?，對于 "從狀態 (i,j) 轉移到 (i + 1,j) 的邊" 的期望通過次數就是?
。
根據期望的線性性質，總期望等于各邊期望貢獻之和，即：
?（因為我們無需計算邊權為0的邊的貢獻，只算?
?即可）
Code:
#include<cstdio>
#include<cstring>
using namespace std;#define N 2005int n,t;
double p,f[N][N],ans;int main()
{scanf("%d%lf%d",&n,&p,&t);f[0][0] = 1.00,ans = 0.00;for (int i = 0;i < t;++ i){f[i + 1][n] += f[i][n];for (int j = 0;j < n;++ j){f[i + 1][j] += f[i][j] * (1.00 - p);f[i + 1][j + 1] += f[i][j] * p;}}for (int i = 0;i < t;++ i)for (int j = 0;j < n;++ j)ans += f[i][j] * p;printf("%.6lf\n",ans);return 0;
}這兩種方法其實體現了期望DP的兩種不同思路，適合仔細琢磨。
