總結的規律：
1.期望可以分解成多個子期望的權重和，權為子期望發生的機率，即 E(aA+bB+…) = aE(A) + bE(B) +…+1；
2.期望從後往前找，一般dp[n]=0,dp[0]是答案；
3.解決過程，找出各種情況乘上這種情況發生的機率，求和；
【1】A - Collecting Bugs
我是題目連結
題意：一個軟體有s個子系統，會産生n種bug。
某人一天發現一個bug，這個bug屬于某種bug，發生在某個子系統中。
求找到所有的n種bug，且每個子系統都找到bug，這樣所要的天數的期望。
需要注意的是：bug的數量是無窮大的，是以發現一個bug，出現在某個子系統的機率是1/s，
屬于某種類型的機率是1/n。
解法：
dp[i][j]表示已經找到i種bug，并存在于j個子系統中，要達到目标狀态的天數的期望。
顯然，dp[n][s]=0，因為已經達到目标了。而dp[0][0]就是我們要求的答案。
dp[i][j]狀态可以轉化成以下四種：
dp[i][j] 發現一個bug屬于已經找到的i種bug和j個子系統中
dp[i+1][j] 發現一個bug屬于新的一種bug，但屬于已經找到的j種子系統
dp[i][j+1] 發現一個bug屬于已經找到的i種bug，但屬于新的子系統
dp[i+1][j+1]發現一個bug屬于新的一種bug和新的一個子系統
以上四種的機率分别為：
p1 = i*j / (n*s)
p2 = (n-i)*j / (n*s)
p3 = i*(s-j) / (n*s)
p4 = (n-i)*(s-j) / (n*s)
又有：期望可以分解成多個子期望的權重和，權為子期望發生的機率，即 E(aA+bB+…) = aE(A) + bE(B) +…
是以：
dp[i,j] = p1*dp[i,j] + p2*dp[i+1,j] + p3*dp[i,j+1] + p4*dp[i+1,j+1] + 1;
整理得：
dp[i,j] = ( 1 + p2*dp[i+1,j] + p3*dp[i,j+1] + p4*dp[i+1,j+1] )/( 1-p1 )
= ( n*s + (n-i)j*dp[i+1,j] + i(s-j)dp[i,j+1] + (n-i)(s-j)*dp[i+1,j+1] )/( n*s - i*j )
代碼：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
double dp[][];
int n,s;
int main()
{
while(~scanf("%d%d",&n,&s))
{
dp[n][s] = ;
for(int i = n; i >= ; i --)
{
for(int j = s; j >= ; j --)
{
if(i == n && j == s) continue;
int p1 = (n - i) * (s - j) * ;
int p2 = (n - i) * j * ;
int p3 = i * (s - j) * ;
int p4 = i * j * ;
dp[i][j] = (p1 * dp[i+][j+] + p2 * dp[i+][j] + p3 * dp[i][j+] + n*s) / (n * s - p4);
}
}
printf("%.4lf\n",dp[][]);
}
}
【2】B - Aeroplane chess
我是題目連結
思考：一個6個面的骰子，很快我就會做到一個有m面的骰子。。。。。這裡還有一個知識點，就是可以直接從一個點到另一個點，不需要扔骰子，那麼dp[i]=dp[go[i]];
題意：
有編号為0-n的格子，從0開始，扔骰子扔到幾就走幾格。有m個瞬移點，每個點可以從格x直接飛到格y，若瞬移到另一個瞬移點可以繼續瞬移。求到達格n的期望扔骰子次數。
思路:
E(i)——到格i期望，E(i)=i是某個瞬移目标點？(E(x)，x指瞬移出發點），否則E(i+1)*1/6+E(i+2)*1/6+…+E(i+6)*1/6+1，注意最後把“又走了一步”加上。标準全期望公式。
代碼：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int go[];
double dp[];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
if(n==&&m==)
{
break;
}
else
{
memset(go,-,sizeof(go));
for(int i=; i<=m; i++)
{
int x,y;
scanf("%d%d",&x,&y);
go[x]=y;
}
memset(dp,,sizeof(dp));
for(int i=n-; i>=; i--)
{
if(go[i]!=-)
{
dp[i]=dp[go[i]];
}
else
{
dp[i]=dp[i+]/+dp[i+]/+dp[i+]/+dp[i+]/+dp[i+]/+dp[i+]/+;
}
}
printf("%.4f\n",dp[]);
}
}
}
【3】F - Dice
我是題目連結
題意:
扔一個有m個面的骰子，每個面有一個數字，這些數字互不相同，求連續扔到n個數相同的期望步數或連續扔到n個數不同的期望步數。
思路：
下面的三個圖檔：不想自己打了：
思考：
一開始沒推出來dp[0]的直接結果，推出來dp[i],dp[i+1],dp[i+2]之間差的等比關系了；
本來想直接寫，寫的時候發現，dp[1]一開始不是已知的；然後就不能直接寫了，還是得推出最後的dp[0],dp[n]的那個式子；好在把dp[0]-dp[1]=1弄明白後其他的就好推出了；
代碼：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
double qiu0(int m,int n)
{
return (pow(m,n)-)/(m-);
}
double qiu1(int m,int n)
{
double ans=;
double p=;
for(int i=; i<n; i++)
{
p=(m*)/((m-i)*)*p;
ans+=p;
}
return ans;
}
int main()
{
int t;
while(~scanf("%d",&t))
{
for(int i=; i<=t; i++)
{
int p,m,n;
scanf("%d%d%d",&p,&m,&n);
if(p==)
{
printf("%.9f\n",qiu0(m,n));
}
else
{
printf("%.9f\n",qiu1(m,n));
}
}
}
}
【4】SPOJ Favorite Dice（數學期望）
無題目連結；
BuggyD loves to carry his favorite die around. Perhaps you wonder why it’s his favorite? Well, his die is magical and can be transformed into an N-sided unbiased die with the push of a button. Now BuggyD wants to learn more about his die, so he raises a question:
What is the expected number of throws of his die while it has N sides so that each number is rolled at least once?
Input
The first line of the input contains an integer t, the number of test cases. t test cases follow.
Each test case consists of a single line containing a single integer N (1 <= N <= 1000) - the number of sides on BuggyD’s die.
Output
For each test case, print one line containing the expected number of times BuggyD needs to throw his N-sided die so that each number appears at least once. The expected number must be accurate to 2 decimal digits.
Example
Input:
2
1
12
Output:
1.00
37.24
題意：
甩一個n面的骰子，問每一面都被甩到的次數期望是多少。
思路：
比較簡單，公式：初始化dp[]=0; dp[i]=i/n*dp[i]+(n-i)/n*dp[i+1]+1; 化簡逆推即可。 求的是dp[0];
思考：這個題的思路跟第一個題很像了；
代碼:
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<memory>
using namespace std;
double dp[];
int main()
{
int T,i,j,n;
scanf("%d",&T);
while(T--){
scanf("%d",&n); dp[n]=;
for(i=n-;i>=;i--) dp[i]=(dp[i+]*(n-i)/n+)*n/(n-i);
printf("%.2lf\n",dp[]);
} return ;
}
【5】E - Crossing Rivers
我是很慢的題目連結
題目大意：
有個人每天要去公司上班，每次會經過N條河，家和公司的距離為D，預設在陸地的速度為1，給出N條河的資訊，包括起始坐标p，寬度L，以及船的速度v。船會往返在河的兩岸，人到達河岸時，船的位置是随機的（往返中）。問說人達到公司所需要的期望時間。
思路：
過每條河最壞的情況是t=3*L/v； 即去的時候船剛剛走。
過沒條河最優的情況是t=L/v； 即去的時候船剛剛來。
由于船是均勻釋出的，符合線性性質，是以平均下來，過每條河的時間t=2*L/v。
思考:
說實話這個題我有點蒙，這麼簡單就可以求了麼，而且p完全沒用上啊；
代碼：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int main()
{
int m,d;
int q=;
while(~scanf("%d%d",&m,&d)&&(m||d))
{
q++;
double ans=;
int p,l,v;
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&p,&l,&v);
ans+=(*l)/(v*);
d=d-l;
}
ans+=d*;
printf("Case %d: %.3f\n\n",q,ans);
}
}
先做了5個，其他的在總結
【6】https://www.cnblogs.com/kuangbin/archive/2012/10/04/2711437.html