求期望两种题型。
1.概率dp
2.高斯消元
这里有一篇很好的文章：http://kicd.blog.163.com/blog/static/126961911200910168335852/
还有kb大神的专题：http://www.cnblogs.com/kuangbin/archive/2012/10/02/2710606.html
先引用大牛文章解释原理
近年的acm竞赛中，数学期望问题常有涉及，在以前也常让本人感到很头疼，近来突然开窍，掌握了基本的分析方法，希望对大家有帮助。写得浅薄，可能数学上不够严谨，只供理解。
首先，来看下期望有啥基本的公式。
第二条式子是今天的主角，他表明了期望有线性的性质，简单理解就是期望之间可根据关系，简单运算（不严谨的理解）。 这就为我们解决一个期望问题，不断转化为解决另外的期望问题，最终转化到一个已知的期望上。
举一个求期望最简单的例子，见下图。
假设有个人在 1号节点处，每一分钟他会缘着边随机走到一个节点或者在原地停留，问他走到4号节点需要平均几分钟？
这是个简单的期望问题，我们用Ei(i=1,2,3,4) 表示从i号节点走到4号节点的数学期望值。根据题意对1号节点有
E1=（1/3）*E1+（1/3）*E2+（1/3）*E3+1 ①
表示 他下一分钟可以走到2或者3或在原地1，每个可能概率是1/3 ,注意是下一分钟，故要加上1.
同理我们对节点2，3同样可以列出
E2=(1/3)*E1+(1/3)*E2+(1/3)*E4+1 ②
E3=(1/3)*E1+(1/3)*E3+(1/3)*E4+1 ③
那E4等于多少呢？很明显E4=0 ④，因为他就是要到点4
这样上面1234式其实就是组成了一组方程组，解方程组就可得出E1！！，用高斯消元，复杂度是O(n^3)
从上述例子，我们可总结出如何解决期望类问题，根据题意，表示出各个状态的期望（上例的Ei，1234）,根据概率公式，列出期望之间的方程，解方程即可。
下面看用上述思路如何解决一道题（poj2096）
原题见附件1。
题意简述：一个人受雇于某公司要找出某个软件的bugs和subcomponents，这个软件一共有n个bugs和s个subcomponents，每次他都能同时随机发现1个bug和1个subcomponent,问他找到所有的bugs和subcomponents的期望次数。
我们用E(i,j)表示他找到了i个bugs和j个subcomponents，离找到n个bugs和s个subcomponents还需要的期望次数，这样要求的就是E(0,0),而E(n,s)=0,对任意的E(i,j),1次查找4种情况，没发现任何新的bugs和subcomponents，发现一个新的bug，发现一个新的subcomponent，同时发现一个新的bug和subcomponent，用概率公式可得：
E(i,j)=1+(i*j/n/s)*E(i,j)+(i*(s-j)/n/s)E(i,j+1)+
((n-i)*j/n/s)*E(i+1,j)+(n-i)*(s-j)/n/s*E(i+1,j+1);
这样根据边界就可解出所有的E(i,j),注意因为当我们找到n个bugs和s个subcomponents就结束，对i>n||j>s均无解的情况，并非期望是0.(数学上常见问题，0和不存在的区别)
那这题是否也是要用高斯消元呢？用高斯消元得话复杂度是O(n^3)，达到10^18 根本是不可解的！！
但其实，注意观察方程，当我们要解E(i,j)的话就需要E(i+1,j),E(I,j+1),E(i+1,j+1), 一开始已知E(n,s)，那其实只要我们从高往低一个个解出I,j就可以了！即可根据递推式解出所有的E(I,j) 复杂度是O(n),10^6 ，完美解决。
代码： 越界的数当作0来处理
dp求期望
逆着递推求解
题意：（题意看题目确实比较难道，n和s都要找半天才能找到）
一个软件有s个子系统，会产生n种bug
某人一天发现一个bug,这个bug属于一个子系统，属于一个分类
每个bug属于某个子系统的概率是1/s,属于某种分类的概率是1/n
问发现n种bug,每个子系统都发现bug的天数的期望。
求解：
dp[i][j]表示已经找到i种bug,j个系统的bug，达到目标状态的天数的期望
dp[n][s]=0;要求的答案是dp[0][0];
dp[i][j]可以转化成以下四种状态:
dp[i][j],发现一个bug属于已经有的i个分类和j个系统。概率为(i/n)*(j/s);
dp[i][j+1],发现一个bug属于已有的分类，不属于已有的系统.概率为 (i/n)*(1-j/s);
dp[i+1][j],发现一个bug属于已有的系统，不属于已有的分类,概率为 (1-i/n)*(j/s);
dp[i+1][j+1],发现一个bug不属于已有的系统，不属于已有的分类,概率为 (1-i/n)*(1-j/s);
整理便得到转移方程
-
#include<iostream>
-
#include<cstdio>
-
using
namespace
std;
-
double dp[
1010][
1010];
-
int main()
-
{
-
int n,s,i,j;
-
while(~
scanf(
"%d%d",&n,&s))
-
{
-
dp[n][s]=
0;
-
for(i=n;i>=
0;i--)
-
{
-
for(j=s;j>=
0;j--){
-
if(i==n&&j==s)
continue;
-
dp[i][j]=(n*s+i*(s-j)*dp[i][j+
1]+(n-i)*j*dp[i+
1][j]+(n-i)*(s-j)*dp[i+
1][j+
1])/(n*s-i*j);
-
}
-
}
-
printf(
"%.4lf\n",dp[
0][
0]);
-
}
-
return
0;
-
}
从上面这道题，我们再次看到了解决期望问题的思路，而且是用到了递推解决问题，其实可递推的原因，当我们把各个状态当成是一个个节点时，概率关系为有向边，我们可看到，可递推的问题其实就是这个关系图是无环的！！那必须要用方程组解决的问题其实就是存在环！！！！而且我还要指出的是用高斯消元的时候，要注意误差的问题，最好把式子适当的增大，避免解小数，否则误差太大，估计也会卡题。
本文到此结束，简单讲解了期望类问题的解决思路，更加深入的学习可参考wc2009两篇的论文，希望能帮到大家！！
Kicd
2009.7.31
hdu4405
有直线坐标1，2，3，。。。。100000
有对应关系a,b a的位置可直接跳到b的位置，a<b
某人投一概率相等的六面骰子，可从x处移到x+i的位置 i=1，2，3，4，5，6，问从0到n位置的投骰子的期望是多少
E(i)=E(i+1)+E(i+2)+E(i+3)+E(i+4)+E(i+5)+E(i+6)+1
-
#include<iostream>
-
#include<cstdio>
-
#include<cstring>
-
#define N 100010
-
using
namespace
std;
-
double dp[N];
-
int jump[N];
-
int main()
-
{
-
int n,m,i,l;
-
while(~
scanf(
"%d%d",&n,&m)&&(n+m)){
-
memset(jump,
0,
sizeof(jump));
-
memset(dp,
0,
sizeof(dp));
-
while(m--)
-
{
-
int a,b;
-
scanf(
"%d%d",&a,&b);
-
jump[a]=b;
-
}
-
for(i=n
-1;i>=
0;i--){
-
if(jump[i])dp[i]=dp[jump[i]];
-
else{
-
for(l=
1;l<=
6;l++)dp[i]+=dp[l+i];
-
dp[i]=dp[i]/
6+
1;
-
}
-
}
-
printf(
"%.4lf\n",dp[
0]);
-
}
-
-
-
return
0;
-
}
hdu3853
迷宫是一个r*c的网格，已知每个网格（i，j）通向（i，j），（i+1，j），（i，j+1）的概率，求从（1，1）走到（r，c）的期望
E(r,c)=P(0)*E(r,c)+P(1)*E(r，c+1)+P(2)*E(r+1，c)+2
-
#include<iostream>
-
#include<cstdio>
-
#include<cstring>
-
#define N 1010
-
using
namespace
std;
-
double dp[N][N];
-
double pro[N][N][
3];
-
int main()
-
{
-
int n,m,i,j,k;
-
while(~
scanf(
"%d%d",&n,&m))
-
{
-
double p;
-
for(i=
1;i<=n;i++)
-
{
-
for(j=
1;j<=m;j++)
-
{
-
for(k=
0;k<
3;k++)
scanf(
"%lf",&pro[i][j][k]);
-
}
-
}
-
dp[n][m]=
0;
-
for(i=n;i>=
1;i--){
-
for(j=m;j>=
1;j--)
-
{
-
if(i==n&&j==m)
continue;
-
if(
1-pro[i][j][
0]<
1e-7)
continue;
-
dp[i][j]=(pro[i][j][
1]*dp[i][j+
1]+pro[i][j][
2]*dp[i+
1][j]+
2)/(
1-pro[i][j][
0]);
-
}
-
}
-
printf(
"%.3lf\n",dp[
1][
1]);
-
}
-
-
return
0;
-
}
BestCoder Round #7 hdu4987
题意： 有一个 面的均匀骰子（[1, ]），然后从 0 出发，根据扔的数字，决定向前走的步数，走到 时就停止。 求刚好在 停止的概率。要求误差1e-5以内。（）
分析：
当 很大时，概率会接近 2.0/(m+1)，当 时，直接返回 2.0/(m+1)
当 时，有：
dp[i] = sigma j < i (dp[j])/m
dp[i-1] = sigma j < i-1 (dp[j])/m
dp[i] - dp[i-1] = dp[i-1]/m
dp[i] = dp[i-1]*(1+1/m)
初值 dp[1] = 1/m
解得：。
当 时：
我们考虑直接 DP，需要用部分和优化到 。
-
#include<iostream>
-
#include<cstdio>
-
#include<algorithm>
-
#include<cstring>
-
#include<cmath>
-
using
namespace
std;
-
#define INF 0x7fffffff
-
#define N 600006
-
double dp[N];
-
int m,n;
-
void work()//优化到O(n+m)
-
{
-
if(n>
600000){
-
printf(
"%.5lf\n",
2.0/(m+
1));
-
return;
-
}
-
int i,j;
-
memset(dp,
0,
sizeof(dp));
-
dp[n]=
1;
-
double tmp=
1.0;
-
if(n<=m)
-
{
-
for(i=n
-1;i>=
0;i--)
-
{
-
dp[i]=tmp/m;
-
tmp=tmp+dp[i];
-
}
-
-
}
-
else{
//n>m
-
for(i=n
-1;i>=n-m;i--)
-
{
-
dp[i]=tmp/m;
-
tmp=tmp+dp[i];
-
}
-
for(;i>=
0;i--)
-
{
-
tmp=tmp-dp[i+
1+m];
-
dp[i]=tmp/m;
-
tmp=tmp+dp[i];
-
}
-
}
-
printf(
"%.5lf\n",dp[
0]);
-
}
-
void work2()
-
{
-
int i,j;
-
memset(dp,
0,
sizeof(dp));
-
dp[n]=
1;
-
for(i=n
-1;i>=
0;i--){
-
for(j=i+
1;j<i+
1+m;j++)
-
{
-
dp[i]+=dp[j]/m;
-
}
-
printf(
"%d %lf\n",i,dp[i]);
-
}
-
printf(
"%.5lf\n",dp[
0]);
-
}
-
-
int main()
-
{
-
while(~
scanf(
"%d%d",&m,&n))
-
{
-
work();
-
}
-
return
0;
-
}
京公网安备 11010502036488号