跟着别人的题表做的
http://blog.csdn.net/tomorrowtodie/article/details/52336931
1.POJ 3744
题意：一条路上有n个地雷，你站在起点1的位置，每次有p的概率走1步，有1-p的概率走2步，
给出n,p,和n个雷的坐标xi,问不踩到地雷的概率
显然f[x]=p*f[x-1]+(1-p)*f[x-2] 然后就是矩阵优化了
2.POJ 3071
有2^i个球队，相邻球队比赛，求最后每个球队获胜的概率
令f[i][j]表示进行了i场比赛 j球队获胜的概率
转移方程就是f[i][j]=sigma(f[i-1][j]*f[i-1][k]*win[j][k]);
Pear和Fish玩游戏游戏：
一个袋子里一开始装着w个白球和b个黑球。
从Pear开始，每次轮流随机抽出一个球。如果抽出的球是白色的，则抽出这个球的人立即获胜。
每当一个球被取出后（然后结算获胜情况后），会有另一个球自动滚出来（不算任何人抽的）。
每个人抽球、和自动滚出来的球都是等概率的。那么Pear获胜率是多少呢？
（以上为原题意抽象成的简单摸球概率问题）
可以用记忆化搜索
1). 跳出的为白色的。概率就是j/(i+j)*(j-1)/(i+j-1)*(i)/(i+j-2)*dp[i-1][j-2]
2). 跳出的位黑色的。概率就是j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2)*dp[i][j-3]
4.POJ 2151
这道题主要就是要容斥成可以求
对于需要满足存在一个点的题目一般都要使用容斥
#include <algorithm> #include <cstdio> #include <iostream> #include <cmath> #include <cstring> using namespace std; double p[1050][35],dp[1050][35][35],sum[1050],sum2[1050]; double ans1,ans2; int n,m,t; int main() { freopen("noip.in","r",stdin); freopen("noip.out","w",stdout); while (cin>>m>>t>>n&&n) { memset(sum,0,sizeof(sum)); memset(sum2,0,sizeof(sum2)); memset(dp,0,sizeof(dp)); for (int i=1;i<=t;i++) for (int j=1;j<=m;j++) cin>>p[i][j]; for (int i=1;i<=t;i++) { dp[i][0][0]=1; for (int j=1;j<=m;j++) dp[i][j][0]=dp[i][j-1][0]*(1-p[i][j]); } for (int i=1;i<=t;i++) { for (int j=1;j<=m;j++) for (int k=1;k<=m;k++) { dp[i][j][k]=dp[i][j-1][k-1]*p[i][j]+dp[i][j-1][k]*(1-p[i][j]); } for (int j=1;j<=n-1;j++) sum[i]+=dp[i][m][j]; for (int j=1;j<=m;j++) sum2[i]+=dp[i][m][j]; } ans1=1; ans2=1; for (int i=1;i<=t;i++) ans1=ans1*sum[i],ans2=ans2*sum2[i]; printf("%.3f ",ans2-ans1); } }
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的系统
- 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;