題目
這題目首先進去以後，沒地方提交，第一次做SGU的題目，只能在HUSTOJ上提交了
有n個盒子，裡面有礼物的，m個人，每個人拿，拿過以後 把礼物取出來 把盒子放回去，求選中礼物數的期望
其實一開始就假設方程 dp[i]為 第i個人獲得礼物的概率，但是狀態轉移方程不知道該怎麼辦，想了很久都沒有辦法，
其實首先邊界為dp[1] = 1 第一個上來選的人肯定必中
接下來一個人的 則由兩部分組成，dp[i] = (1 - dp[i - 1]) * dp[i - 1] + .........，因為上一個人若沒有選中，那麼這一次選中的概率跟是上一個一樣的，那麼如果上一個人選中了呢，真的是想了好久好久啊，可是沒有思路，，最後沒辦法，看了別的博客，那個人用了一個公式的方法做的，但是我覺得概率DP可以推的，看他介紹，一開始就強調了m個人選礼物是相互獨立的事件，呃，這時候我有點開竅了，概率論學了很久了，有點忘了，每一次當一個礼物被選走的時候，人們選中礼物的概率都會減少1/n，這麼說吧，我的理解是一開始選就是n個裡面選一個，再後來少了一個礼物，那選中的概率就少了1/n，比如一開始有五個礼物，那麼一開始選中的的概率為1，第二次按照我所想就是4/5，實際上確實 是只剩下四個礼物了，但是空盒子還是有一個的，所以一個人選中的概率為4/5，前面做多了，後來我一直以為是1/4，忘了總體，前面人選走礼物 對於這次 你的選擇沒有影響，因為你還是在那麼多盒子裡選，總得選得范圍並沒有發生變化，那麼這樣方程另一部分就出來了
dp[i] = (1 - dp[i - 1]) * dp[i - 1] + dp[i - 1] * (dp[i - 1] - 1/n)//對這個有點疑問的，題目沒說n比m大，萬一n比m小，一直減，會不會為負？
應該是我想多了，後面被拿完了礼物，那麼一直都是0了，就算是負的乘以0也是一樣的
那麼這樣m個人每個人 獲得礼物的概率都求出來了，如何求期望呢？哈哈真的不會唉，概率忘光了...我當時的想法就是 每個人的概率乘以1然後累加，嘗試了案例是對了，交了以後就過了。。。到底是為什麼捏，看了別人博客都沒有給出解釋。。。百度了一會獨立事件的期望，有個n * p的我都知道的方法，還發現了一個二項分布的計算方法，這個我是忘了，但是稍微畫了一會，發現 跟這道題還是沒有聯系上，路過的巨巨 請給個解釋，太晚了，明天自己再研究研究
int n,m;
double dp[100000 + 55];
void init() {
}
bool input() {
while(cin>>n>>m) {
return false;
}
return true;
}
void cal() {
dp[1] = 1.00;
for(int i=2;i<=m;i++)
dp[i] = dp[i - 1] * (dp[i - 1] - 1.00/n*1.0) + dp[i - 1] * (1 - dp[i - 1]);
double ans = 0.00;
for(int i=1;i<=m;i++)
ans += dp[i] * 1.00;
printf("%.10lf\n",ans);
}
void output() {
}
int main() {
while(true) {
init();
if(input())return 0;
cal();
output();
}
return 0;
}
哎呀，寫完題解以後，走之前又手賤的試了一把，嗯發現這樣也是可以的，就是每一步都加一個步數1，跟以前圖裡走步數其實是一樣的，因為dp[i]代表的是選中的概率，那麼肯定是選中的，所以加1就沒問題了，那麼加1狀態方程就變成了，dp[i]代表的是前i個人選礼物數目的期望，直到dp[m]就是答案，但是這樣其它方向一想有點問題了，這樣不是m步了嗎？跟礼物數什麼聯系呢？其實沒事，如果n大於m，那麼其實你最多選m個礼物，如果n小於m，那麼後來的概率是有為0的，所以你這樣加上去，在下一步的乘法又變成了0，亂七八糟，否定自己以後又肯定自己，呵呵，好煩啊，睡覺去了。。。
int n,m;
double dp[100000 + 55];
void init() {
}
bool input() {
while(cin>>n>>m) {
return false;
}
return true;
}
void cal() {
dp[1] = 1.00;
for(int i=2;i<=m;i++)
dp[i] = dp[i - 1] * (dp[i - 1] - 1.00/n*1.0) + dp[i - 1] * (1 - dp[i - 1]) + 1;
//double ans = 0.00;
//for(int i=1;i<=m;i++)
// ans += dp[i] * 1.00;
printf("%.10lf\n",dp[m]);
}
void output() {
}
int main() {
while(true) {
init();
if(input())return 0;
cal();
output();
}
return 0;
}
最後n個礼物都不被選中的期望為 n *( (n - 1)/n)^m,
那麼選中礼物 的 期望為n - n *( (n - 1)/n)^m,哈哈,跪了，啥好都不如數學好啊，想了那麼久，人家一句話 簡單概率期望公式 就解決了，呵呵
int n,m;
double dp[100000 + 55];
void init() {
}
bool input() {
while(cin>>n>>m) {
return false;
}
return true;
}
void cal() {
double ans = n * 1.00;
double tmp = 1.00;
for(int i=1;i<=m;i++) {
tmp *= (n - 1)*1.0/n*1.0;
}
ans = ans - n * tmp;
printf("%.10lf\n",ans);
}
void output() {
}
int main() {
while(true) {
init();
if(input())return 0;
cal();
output();
}
return 0;
}
