概率DP入门小结
高飞翮
说是概率DP，其实主要是求概率和期望的问题
说到DP总要有状态，每种状态可能有多种子状态
一般的DP是这样：在DP过程中，当前状态必然是由多个子状态中的最优的转移而来
所以一般的DP求的是最优的结果
而概率不需要最优，而是实际概率
所以概率DP最大的区别在于：在DP过程中，当前状态是由所有子状态的概率共同转移而来
所以概率DP只是利用了DP的动态而没有规划 （只有状态转移，而不需要进行决策）
至于状态转移方程怎么列，最科学的自然是根据数学知识列，
不过实际做题中会发现找规律也是一种不错的方法，
而事实证明，如果可以状态转移，找规律的方法往往是可行的
不过数学扎实的话用数学知识绝对要比找规律快且准
POJ 3744 (矩阵优化)
题意：一条路上有n个地雷，你站在起点1的位置，每次有p的概率走1步，有1-p的概率走2步，
给出n,p,和n个雷的坐标xi,问不踩到地雷的概率
数据范围 ： 1 <= n <= 10 ,0.25 <= p <= 0.75 ,1 <= xi <= 10^8
分析：
显然有雷的点比没有雷的点多得多，所以计算踩到雷的概率要比计算不踩到雷的概率简单
将路分为n段，（1~x1,x1~x2,x2~x3,...,xn-1~xn）单独计算每段踩到雷的概率,
利用乘法原理求出踩到雷的总概率，不踩到雷的概率 = 1 - 踩到雷的概率
dp[i]表示到达i点的概率
dp[i] = p*dp[i-1]+(1-p)*dp[i-2]
坐标数据太大，直接乘肯定不行，这个时候就需要用到矩阵快速幂
上面dp的状态转移方程其实和斐波那契数列的表达式很像不是吗^_^
用一样的原理构造矩阵就好了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
struct Matrix
{
double mat[2][2];
};
Matrix operator * (Matrix a,Matrix b)
{
Matrix c;
for (int i = 0;i < 2;++i)
{
for (int j = 0;j < 2;++j)
{
c.mat[i][j] = 0;
for (int k = 0;k < 2;++k)
{
c.mat[i][j] += a.mat[i][k]*b.mat[k][j];
}
}
}
return c;
}
Matrix operator ^ (Matrix a,ll k)//矩阵幂
{
Matrix c;
memset(c.mat,0,sizeof(c.mat));
for(int i=0;i<2;i++)c.mat[i][i]=1;//初始化为单位矩阵
//据说任何矩阵乘以单位矩阵其值不会变
for (;k;k>>=1)
{
if (k&1) c = c*a;
a = a*a;
}
return c;
}
int x[111];
int main()
{
int n;double p;
while (cin>>n>>p)
{
for (int i = 0;i < n;++i) scanf("%d",x+i);
sort(x,x+n);
double ans = 1.0;
Matrix c;
c.mat[0][0] = p,c.mat[0][1] = 1.0-p;
c.mat[1][0] = 1.0,c.mat[1][1] = 0.0;
Matrix a = c^(x[0]-1);
ans *= (1-a.mat[0][0]);
for (int i = 1;i < n;++i)
{
if (x[i] == x[i-1]) continue;
a = c^(x[i]-x[i-1]-1);
ans *= (1.0-a.mat[0][0]);
}
printf("%.7f\n",ans);
}
return 0;
}POJ 3071
全概率问题：
当前场次要与j比赛的队伍x是哪个？而x能与j比必然是胜过了对手
dp[i][j]表示第i次比赛j赢的概率
dp[i][j] += dp[i-1][j]*dp[i-1][t]*p[j][t]
其中t是第i次比赛可能与j相邻的队伍
第奇数个赢家和前一个赢家比赛
第偶数个赢家和后一个赢家比赛
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define SDB(n) scanf("%lf",&n)
#define Schar(n) scanf("%c",&n)
#define Schars(s) scanf("%s",s)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 8;
double dp[N][1<<N];//dp[i][j]表示第i次比赛j赢的概率
/*
dp[i][j] += dp[i-1][j]*dp[i-1][t]*p[j][t]
其中t是第i次比赛可能与j相邻的队伍
第奇数个赢家和前一个赢家比赛
第偶数个赢家和后一个赢家比赛
*/
int n;double p[1<<N][1<<N];
int main()
{
while (Sint(n),~n)
{
for (int i = 0;i < (1<<n);++i)
{
for (int j = 0;j < (1<<n);++j)
{
SDB(p[i][j]);
}
}
mem(dp,0);
for (int i = 0;i < (1<<n);++i) dp[0][i] = 1;
for (int i = 1;i <= n;++i)//进行n场比赛
{
for (int j = 0;j < (1<<n);++j)
{
int t = j>>(i-1);//j是第t个胜者
if (t&1)//奇数与j-1比
{
for (int k = t*(1<<(i-1))-1;k >= (t-1)*(1<<(i-1));--k)
{
dp[i][j] += dp[i-1][j]*dp[i-1][k]*p[j][k];
}
}
else //偶数与j+1比
{
for (int k = (t+1)*(1<<(i-1));k < (t+2)*(1<<(i-1));++k)
{
dp[i][j] += dp[i-1][j]*dp[i-1][k]*p[j][k];
}
}
}
}
int mx = 0;
for (int i = 0;i < (1<<n);++i)
{
if (dp[n][i]>dp[n][mx]) mx = i;
}
Pintc(mx+1,'\n');
}
return 0;
}CodeForces 148D
Pear和Fish玩游戏游戏：
一个袋子里一开始装着w个白球和b个黑球。
从Pear开始，每次轮流随机抽出一个球。如果抽出的球是白色的，则抽出这个球的人立即获胜。
每当一个球被取出后（然后结算获胜情况后），会有另一个球自动滚出来（不算任何人抽的）。
每个人抽球、和自动滚出来的球都是等概率的。那么Pear获胜率是多少呢？
（以上为原题意抽象成的简单摸球概率问题）
dp[i][j]表示Peal摸球时剩余i个白球和j个黑球的胜率
#define mem(a,x) memset(a,x,sizeof(a))
#define EX2(x) ((x)*(x))
#define EX3(x) ((x)*(x)*(x))
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define SDB(n) scanf("%lf",&n)
#define Schar(n) scanf("%c",&n)
#define Schars(s) scanf("%s",s)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define SDB2(n,x) scanf("%lf%lf",&n,&x)
#define Schar2(n,x) scanf("%c%c",&n,&x)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
#define PDB(x,c) printf("%f%c",x,c)
#define PDB1(x,c) printf("%.1f%c",x,c)
#define PDB2(x,c) printf("%.2f%c",x,c)
#define PDB3(x,c) printf("%.3f%c",x,c)
#define PDB4(x,c) printf("%.4f%c",x,c)
#define PDB5(x,c) printf("%.5f%c",x,c)
#define PDB6(x,c) printf("%.6f%c",x,c)
#define PDB7(x,c) printf("%.7f%c",x,c)
#define PDB8(x,c) printf("%.8f%c",x,c)
#define PDB9(x,c) printf("%.9f%c",x,c)
#define esp 1e-7
#define mod
#define ls i<<1
#define rs i<<1|1
#define m(i) ((q[i].l+q[i].r)>>1)
using namespace std;
typedef long long ll;
typedef double DB;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
/*
dp[i][j]表示Peal摸球时剩余i个白球和j个黑球的胜率
*/
const int N = 1111;
int w,b;
double dp[N][N];
void getdp(double &d,double x,double y,int i,int j)
{
if (j>=2) d += y/(x+y)*(y-1.0)/(x+y-1.0)* x /(x+y-2.0)*dp[i-1][j-2];
if (j>=3) d += y/(x+y)*(y-1.0)/(x+y-1.0)*(y-2.0)/(x+y-2.0)*dp[i][j-3];
}
int main()
{
while (cin>>w>>b)
{
for (int i = 1;i <= w;++i) dp[i][0] = 1;//全白球必胜
for (int j = 1;j <= b;++j) dp[0][j] = 0;//全黑球必输
for (int i = 1;i <= w;++i)
{
for (int j = 1;j <= b;++j)
{
dp[i][j] = i*1.0/(DB)(i+j);
getdp(dp[i][j],i,j,i,j);
}
}
printf("%.9f\n",dp[w][b]);
}
return 0;
}POJ 2151
M个问题，T个队伍，冠军至少解决N题
p[i][j]表示队伍i解决j题的概率
求所有队至少解决1题并且冠军至少解决N题的概率
不用管谁是冠军，只有有人解决了N题，冠军一定满足了
ans = P1(每队至少1题) - P2(每队至少1题但不超过n-1题)
dp[i][j]表示第i个队解出的题目小于等于j的概率
f[i][j][k]表示第i个队在前j题解出k题的概率
f[i][j][k] = f[i][j-1][k-1]*p[i][j]+p[i][j-1][k]*(1-p[i][j])
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#define mem(a,x) memset(a,x,sizeof(a))
#define sqrt(n) sqrt((double)n)
#define EX2(x) ((x)*(x))
#define EX3(x) ((x)*(x)*(x))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define SDB(n) scanf("%lf",&n)
#define Schar(n) scanf("%c",&n)
#define Schars(s) scanf("%s",s)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define SDB2(n,x) scanf("%lf%lf",&n,&x)
#define Schar2(n,x) scanf("%c%c",&n,&x)
#define Sint3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
#define PDB(x,c) printf("%f%c",x,c)
#define PDB1(x,c) printf("%.1f%c",x,c)
#define PDB2(x,c) printf("%.2f%c",x,c)
#define PDB3(x,c) printf("%.3f%c",x,c)
#define PDB4(x,c) printf("%.4f%c",x,c)
#define PDB5(x,c) printf("%.5f%c",x,c)
#define PDB6(x,c) printf("%.6f%c",x,c)
#define PDB7(x,c) printf("%.7f%c",x,c)
#define PDB8(x,c) printf("%.8f%c",x,c)
#define PDB9(x,c) printf("%.9f%c",x,c)
#define _M_ %
#define _C_ ^
#define _F_ 5
#define _S_ 6
#define _A_ ~
#define esp 1e-7
#define mod
#define ls i<<1
#define rs i<<1|1
#define m(i) ((q[i].l+q[i].r)>>1)
using namespace std;
typedef long long ll;
typedef double DB;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
//const int dx[] = {-1,-1,-1,0,0,1,1,1};
//const int dy[] = {-1,0,1,-1,1,-1,0,1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
/*
M个问题，T个队伍，冠军至少解决N题
p[i][j]表示队伍i解决j题的概率
求所有队至少解决1题并且冠军至少解决N题的概率
不用管谁是冠军，只有有人解决了N题，冠军一定满足了
ans = P1(每队至少1题) - P2(每队至少1题但不超过n-1题)
dp[i][j]表示第i个队解出的题目小于等于j的概率
f[i][j][k]表示第i个队在前j题解出k题的概率
f[i][j][k] = f[i][j-1][k-1]*p[i][j]+p[i][j-1][k]*(1-p[i][j])
*/
const int N = 1111;
DB dp,f[2][111],p[N][N];
int main()
{
int m,t,n;
while (Sint3(m,t,n)&&(m||t||n))
{
DB P1 = 1.0,P2 = 1.0;
for (int i = 1;i <= t;++i)
{
DB _ = 1.0;
for (int j = 1;j <= m;++j)
{
cin>>p[i][j];
_ = _*(1.0-p[i][j]);
}
P1 = P1*(1.0-_);
}
for (int i = 1;i <= t;++i)
{
int _ = 0;
mem(f,0);
f[0][0] = 1.0;
for (int j = 1;j <= m;++j)
{
_=_^1;
for (int k = 1;k <= m;++k)
{
f[_][k] = p[i][j]*f[_ _C_ 1][k-1]+(1-p[i][j])*f[_ _C_ 1][k];
}
f[_][0] = f[_ _C_ 1][0]*(1-p[i][j]);
}
dp = 0.0;
for (int j = 1;j < n;++j) dp += f[_][j];
P2 *= dp;
}
PDB3(P1-P2,'\n');
}
return 0;
}POJ 2096
题目的状态有点繁琐
bug的种类，系统是否中毒
当发现一个bug，可能是新的种类，可能造成新的系统中毒
一共是4种情况：
dp[i][j]表示已经发现了i种bug且已经发现j个系统有bug所需要的天数
1.dp[i-1][j-1] //新种类的bug 和新的系统
2.dp[i-1][j] //新种类的bug 已经有bug的系统
3.dp[i][j-1]//已有种类的bug 新系统
4.dp[i][j] //已有种类的bug 已经有bug的系统
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#define mem(a,x) memset(a,x,sizeof(a))
#define sqrt(n) sqrt((double)n)
#define EX2(x) ((x)*(x))
#define EX3(x) ((x)*(x)*(x))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define SDB(n) scanf("%lf",&n)
#define Schar(n) scanf("%c",&n)
#define Schars(s) scanf("%s",s)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define SDB2(n,x) scanf("%lf%lf",&n,&x)
#define Schar2(n,x) scanf("%c%c",&n,&x)
#define Sint3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
#define PDB(x,c) printf("%f%c",x,c)
#define PDB1(x,c) printf("%.1f%c",x,c)
#define PDB2(x,c) printf("%.2f%c",x,c)
#define PDB3(x,c) printf("%.3f%c",x,c)
#define PDB4(x,c) printf("%.4f%c",x,c)
#define PDB5(x,c) printf("%.5f%c",x,c)
#define PDB6(x,c) printf("%.6f%c",x,c)
#define PDB7(x,c) printf("%.7f%c",x,c)
#define PDB8(x,c) printf("%.8f%c",x,c)
#define PDB9(x,c) printf("%.9f%c",x,c)
#define _M_ %
#define _C_ ^
#define _F_ 5
#define _S_ 6
#define _A_ ~
#define esp 1e-7
#define mod
#define ls i<<1
#define rs i<<1|1
#define m(i) ((q[i].l+q[i].r)>>1)
using namespace std;
typedef long long ll;
typedef double DB;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
//const int dx[] = {-1,-1,-1,0,0,1,1,1};
//const int dy[] = {-1,0,1,-1,1,-1,0,1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
/*
n 种 bug s 个系统
1.n种bug全部出现
2.s个系统全部有bug
dp[i][j]表示已经发现了i种bug且已经发现j个系统有bug所需要的天数
1.dp[i-1][j-1] //新种类的bug 和新的系统
2.dp[i-1][j] //新种类的bug 已经有bug的系统
3.dp[i][j-1]//已有种类的bug 新系统
4.dp[i][j] //已有种类的bug 已经有bug的系统
p1 = (n-i)*(s-j)/(n*s)
p2 = (n-i)*j/(n*s)
p3 = i*(s-j)/(n*s)
p4 = i*j/(n*s)
*/
const int N = 1111;
DB dp[N][N];
int main()
{
int n,s;
while (cin>>n>>s)
{
mem(dp,0);
for (int i = n;i >= 0;--i)
{
for (int j = s;j >= 0;--j)
{
if (i == n&&j == s) continue;
DB p1 = (n-i)*(s-j)*1.0;
DB p2 = (n-i)*j*1.0;
DB p3 = i*(s-j)*1.0;
DB p4 = 1.0*n*s - i*j*1.0;
dp[i][j] = (p1*dp[i+1][j+1]+p2*dp[i+1][j]+p3*dp[i][j+1] + 1.0*n*s)/p4;
// cout<<dp[i][j]<<endl;
}
}
// cout<<dp[0][0]<<endl;
PDB4(dp[0][0],'\n');
}
return 0;
}HDU 3853
dp[i][j]表示在[i,j]处到达终点的期望
dp[i][j] = p1*dp[i][j] + p2*dp[i][j+1] + p3*dp[i+1][j] + 2
dp[i][j] = (p2*dp[i][j+1] + p3*dp[i+1][j] + 2)/(1-p1)
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#define mem(a,x) memset(a,x,sizeof(a))
#define sqrt(n) sqrt((double)n)
#define EX2(x) ((x)*(x))
#define EX3(x) ((x)*(x)*(x))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define SDB(n) scanf("%lf",&n)
#define Schar(n) scanf("%c",&n)
#define Schars(s) scanf("%s",s)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define SDB2(n,x) scanf("%lf%lf",&n,&x)
#define Schar2(n,x) scanf("%c%c",&n,&x)
#define Sint3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define Sll3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define SDB3(x,y,z) scanf("%lf %lf %lf",&x,&y,&z)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
#define PDB(x,c) printf("%f%c",x,c)
#define PDB1(x,c) printf("%.1f%c",x,c)
#define PDB2(x,c) printf("%.2f%c",x,c)
#define PDB3(x,c) printf("%.3f%c",x,c)
#define PDB4(x,c) printf("%.4f%c",x,c)
#define PDB5(x,c) printf("%.5f%c",x,c)
#define PDB6(x,c) printf("%.6f%c",x,c)
#define PDB7(x,c) printf("%.7f%c",x,c)
#define PDB8(x,c) printf("%.8f%c",x,c)
#define PDB9(x,c) printf("%.9f%c",x,c)
#define _M_ %
#define _C_ ^
#define _F_ 5
#define _S_ 6
#define _A_ ~
#define esp 1e-7
#define mod
#define ls i<<1
#define rs i<<1|1
#define m(i) ((q[i].l+q[i].r)>>1)
using namespace std;
typedef long long ll;
typedef double DB;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
//const int dx[] = {-1,-1,-1,0,0,1,1,1};
//const int dy[] = {-1,0,1,-1,1,-1,0,1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
/*
dp[i][j]表示在[i,j]处到达终点的期望
dp[i][j] = p1*dp[i][j] + p2*dp[i][j+1] + p3*dp[i+1][j] + 2
dp[i][j] = (p2*dp[i][j+1] + p3*dp[i+1][j] + 2)/(1-p1)
*/
const int N = 1111;
struct node
{
DB p1,p2,p3;
}p[N][N] ;
DB dp[N][N];
int main()
{
int r,c;
while (Sint2(r,c) == 2)
{
for (int i = 1;i <= r;++i)
{
for (int j = 1;j <= c;++j)
{
node &t = p[i][j];
SDB3(t.p1,t.p2,t.p3);
}
}
mem(dp,0);
for (int i = r;i >= 1;--i)
{
for (int j = c;j >= 1;--j)
{
if (i==r&&j==c) continue;
node &t = p[i][j];
if (fabs(t.p1 - 1.0)<esp) continue;
dp[i][j] = t.p2*dp[i][j+1] + t.p3*dp[i+1][j] + 2.0;
dp[i][j] /= (1.0 - t.p1);
}
}
PDB3(dp[1][1],'\n');
}
return 0;
}飞行棋游戏，到达坐标大于等于n就胜利
有可以从x直接飞到y的点
掷骰子（1-6），问胜利的期望掷骰子次数
从终点往起点推（因为终点的期望是已知的 -- 0）
如果是不能飞的点i，子状态就是（i+j）(1<=j<=6)
可以飞的点i，子状态就是所有可以飞到i点的状态
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#define mem(a,x) memset(a,x,sizeof(a))
#define sqrt(n) sqrt((double)n)
#define EX2(x) ((x)*(x))
#define EX3(x) ((x)*(x)*(x))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define SDB(n) scanf("%lf",&n)
#define Schar(n) scanf("%c",&n)
#define Schars(s) scanf("%s",s)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define SDB2(n,x) scanf("%lf%lf",&n,&x)
#define Schar2(n,x) scanf("%c%c",&n,&x)
#define Sint3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define Sll3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define SDB3(x,y,z) scanf("%lf %lf %lf",&x,&y,&z)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
#define PDB(x,c) printf("%f%c",x,c)
#define PDB1(x,c) printf("%.1f%c",x,c)
#define PDB2(x,c) printf("%.2f%c",x,c)
#define PDB3(x,c) printf("%.3f%c",x,c)
#define PDB4(x,c) printf("%.4f%c",x,c)
#define PDB5(x,c) printf("%.5f%c",x,c)
#define PDB6(x,c) printf("%.6f%c",x,c)
#define PDB7(x,c) printf("%.7f%c",x,c)
#define PDB8(x,c) printf("%.8f%c",x,c)
#define PDB9(x,c) printf("%.9f%c",x,c)
#define _M_ %
#define _C_ ^
#define _F_ 5
#define _S_ 6
#define _A_ ~
#define esp 1e-7
#define mod
#define ls i<<1
#define rs i<<1|1
#define m(i) ((q[i].l+q[i].r)>>1)
using namespace std;
typedef long long ll;
typedef double DB;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
//const int dx[] = {-1,-1,-1,0,0,1,1,1};
//const int dy[] = {-1,0,1,-1,1,-1,0,1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
/*
dp[i]表示在i点到达胜利的期望
if i > n dp[i] = 0
如果i点可以飞：
dp[i] = dp[i+(1~6)]/6 + 1
如果i点不能飞：
dp[i] = 所有i点可以飞到的点的期望和除以这些点的个数
*/
const int N = 100010;
vector<int>u[N];//我在想的是连环飞 ?
DB dp[N];
int main()
{
int n,m;
while (cin>>n>>m)
{if ((!n)&&(!m)) break;
mem(u,0);
mem(dp,0);
for (int i = 1,x,y;i <= m;++i)
{
Sint2(x,y);
u[x].push_back(y);//x可以到达y
}
for (int i = n-1;i >= 0;--i)
{
if (u[i].size())
{
DB sum = 0.0;
DB t = 0;
for (int j = 0;j < u[i].size();++j)
{
int v = u[i][j];
// cout<<v<<" ";
sum += dp[v];
++t;
}
// cout<<endl;
dp[i] = sum/t;
}
else
{
DB sum = 0.0, t = 0.0;
for (int j = 1;j <= 6;++j)
{
sum += dp[i+j];
++t;
}
dp[i] = sum/t + 1.0;
}
// cout<<i<<" : "<<dp[i]<<endl;
}
PDB4(dp[0],'\n');
}
return 0;
}HDU 4336
集齐所有卡片的期望卡片数
首先是可能某个零食里面没有卡片有一个概率p0
其次是可能这个卡片是已经拥有的卡片，是不起作用的
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#define mem(a,x) memset(a,x,sizeof(a))
#define sqrt(n) sqrt((double)n)
#define EX2(x) ((x)*(x))
#define EX3(x) ((x)*(x)*(x))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define SDB(n) scanf("%lf",&n)
#define Schar(n) scanf("%c",&n)
#define Schars(s) scanf("%s",s)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define SDB2(n,x) scanf("%lf%lf",&n,&x)
#define Schar2(n,x) scanf("%c%c",&n,&x)
#define Sint3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define Sll3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define SDB3(x,y,z) scanf("%lf %lf %lf",&x,&y,&z)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
#define PDB(x,c) printf("%f%c",x,c)
#define PDB1(x,c) printf("%.1f%c",x,c)
#define PDB2(x,c) printf("%.2f%c",x,c)
#define PDB3(x,c) printf("%.3f%c",x,c)
#define PDB4(x,c) printf("%.4f%c",x,c)
#define PDB5(x,c) printf("%.5f%c",x,c)
#define PDB6(x,c) printf("%.6f%c",x,c)
#define PDB7(x,c) printf("%.7f%c",x,c)
#define PDB8(x,c) printf("%.8f%c",x,c)
#define PDB9(x,c) printf("%.9f%c",x,c)
#define _M_ %
#define _C_ ^
#define _F_ 5
#define _S_ 6
#define _A_ ~
#define esp 1e-7
#define mod
#define ls i<<1
#define rs i<<1|1
#define m(i) ((q[i].l+q[i].r)>>1)
using namespace std;
typedef long long ll;
typedef double DB;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
//const int dx[] = {-1,-1,-1,0,0,1,1,1};
//const int dy[] = {-1,0,1,-1,1,-1,0,1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
DB dp[1<<21],p[22];
//dp[st]表示该状态下收集所有的卡片的期望
//st中1表示该卡片收集到了,0表示没有收集到
int main()
{
int n;
while(cin>>n)
{
double p0 = 1.0;//没有卡片的概率
for (int i = 0;i < n;++i)
{
SDB(p[i]);
p0 -= p[i];
}
int V = (1<<n)-1;
dp[V] = 0;//所有卡片都有了 期望是0
for (int i = V-1;i >= 0;--i)
{
DB pz = p0,ans = 0.0;//pz表示获得已经拥有的卡片，相当于没有获得卡片
for (int j = 0;j < n;++j)
{
if (i&(1<<j))//j卡片已经有啦
{
pz += p[j];
}
else //获得这张卡片
{
ans += p[j]*(dp[i^(1<<j)]+1.0);
}
dp[i] = (ans+pz)/(1.0-pz);
}
}
PDB4(dp[0],'\n');
}
return 0;
}HDU 4652 （期望）
掷出连续n次相同或不同的期望
猜到到等比，证明出来的也是等比
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#define mem(a,x) memset(a,x,sizeof(a))
#define sqrt(n) sqrt((double)n)
#define EX2(x) ((x)*(x))
#define EX3(x) ((x)*(x)*(x))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define SDB(n) scanf("%lf",&n)
#define Schar(n) scanf("%c",&n)
#define Schars(s) scanf("%s",s)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define SDB2(n,x) scanf("%lf%lf",&n,&x)
#define Schar2(n,x) scanf("%c%c",&n,&x)
#define Sint3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define Sll3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define SDB3(x,y,z) scanf("%lf %lf %lf",&x,&y,&z)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
#define PDB(x,c) printf("%f%c",x,c)
#define PDB1(x,c) printf("%.1f%c",x,c)
#define PDB2(x,c) printf("%.2f%c",x,c)
#define PDB3(x,c) printf("%.3f%c",x,c)
#define PDB4(x,c) printf("%.4f%c",x,c)
#define PDB5(x,c) printf("%.5f%c",x,c)
#define PDB6(x,c) printf("%.6f%c",x,c)
#define PDB7(x,c) printf("%.7f%c",x,c)
#define PDB8(x,c) printf("%.8f%c",x,c)
#define PDB9(x,c) printf("%.9f%c",x,c)
#define _M_ %
#define _C_ ^
#define _F_ 5
#define _S_ 6
#define _A_ ~
#define esp 1e-7
#define mod
#define ls i<<1
#define rs i<<1|1
#define m(i) ((q[i].l+q[i].r)>>1)
using namespace std;
typedef long long ll;
typedef double DB;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
//const int dx[] = {-1,-1,-1,0,0,1,1,1};
//const int dy[] = {-1,0,1,-1,1,-1,0,1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
/*
dp[i]表示已经掷出i个相同的面的期望
dp[n] = 0 //已有n个就不需要了
dp[i] = 1/m * dp[i+1] + (m-1)/m*dp[1] + 1
dp[i+1] = 1/m * dp[i+2] + (m-1)/m * dp[1] + 1
两式相减得dp[i+1] - dp[i] = 1/m * (dp[i+2] - d[i+1])
可以发现任意连续的两数之差成等比数列，就可以求出dp[0]。
不同的面同理
*/
int main()
{
int T;
while (cin>>T)
{
while (T--)
{
int op,m,n;
Sint3(op,m,n);
DB ans = 1.0;
if (op == 0)//同
{
DB p = (DB)m,_ = (DB)m;
for (int i = 1;i <= n-1;++i)
{
ans += _;
_*=p;
}
}
else //不同
{
DB _ = 1.0;
for (int i = 1;i <= n-1;++i)
{
_*=m*1.0/(m-i);
ans += _;
}
}
PDB9(ans,'\n');
}
}
return 0;
}HDU 4035 (树形DP+期望)
这题esp开得不够小会WA ,利用非常繁复的数学知识去证明
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#define mem(a,x) memset(a,x,sizeof(a))
#define sqrt(n) sqrt((double)n)
#define EX2(x) ((x)*(x))
#define EX3(x) ((x)*(x)*(x))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define SDB(n) scanf("%lf",&n)
#define Schar(n) scanf("%c",&n)
#define Schars(s) scanf("%s",s)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define SDB2(n,x) scanf("%lf%lf",&n,&x)
#define Schar2(n,x) scanf("%c%c",&n,&x)
#define Sint3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define Sll3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define SDB3(x,y,z) scanf("%lf %lf %lf",&x,&y,&z)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
#define PDB(x,c) printf("%f%c",x,c)
#define PDB1(x,c) printf("%.1f%c",x,c)
#define PDB2(x,c) printf("%.2f%c",x,c)
#define PDB3(x,c) printf("%.3f%c",x,c)
#define PDB4(x,c) printf("%.4f%c",x,c)
#define PDB5(x,c) printf("%.5f%c",x,c)
#define PDB6(x,c) printf("%.6f%c",x,c)
#define PDB7(x,c) printf("%.7f%c",x,c)
#define PDB8(x,c) printf("%.8f%c",x,c)
#define PDB9(x,c) printf("%.9f%c",x,c)
#define PCase() printf("Case %d: ",++kas)
#define Pcase() printf("case %d: ",++kas)
#define esp 1e-9
#define mod
#define ls i<<1
#define rs i<<1|1
#define m(i) ((q[i].l+q[i].r)>>1)
using namespace std;
typedef long long ll;
typedef double DB;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
//const int dx[] = {-1,-1,-1,0,0,1,1,1};
//const int dy[] = {-1,0,1,-1,1,-1,0,1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int N = 10004;
DB k[N],e[N];DB A,B,C;//A B C在叶子的时候是初始化
vector<int>s[N];
void dfs(int node,int fa)
{
DB a = 0,b = 0,c = 0;
for (int i = 0;i < s[node].size();++i)
{
int son = s[node][i];
if (son == fa) continue;
dfs(son,node);
a+=A,b+=B,c+=C;
}
int t = s[node].size();
DB p = (1.0 - k[node] - e[node])/t;
A = (k[node]+p*a)/(1.0-p*b);
B = p/(1-p*b);
C = (1-k[node]-e[node]+p*c)/(1-p*b);
}
int main()
{
int T;cin>>T;int kas = 0;
while (T--)
{
int n;cin>>n; mem(s,0);
for (int i = 1,x,y;i < n;++i)
{
Sint2(x,y);
s[x].push_back(y);
s[y].push_back(x);
}
for (int i = 1;i <= n;++i)
{
SDB2(k[i],e[i]);
k[i]/=100.0;
e[i]/=100.0;
}
dfs(1,-1);
PCase();
if (fabs(A-1)<esp) puts("impossible");
else PDB(C/(1.0-A),'\n');
}
return 0;
}总的来说概率DP与数学息息相关，基本算是属于数学的范畴
类似资料：