初中课本知识已经有讲概率啦！应用在信息学里面可以这样↓
我们现在假装要从出生点出发去新日$♂$暮里，有两种方法
老司机开车带我们去，费用是一千软妹币，绝对不翻车
年轻司机开车带我们去，费用是一百软妹币，但是有$0.5$的概率会翻车被查。因此我们要回到出生点，此时只能让老司机带我们飞【捂眼
上谁的车呢？
权衡利弊之后，我们应当先上年轻司机的车试试看
此时年轻司机有$0.5$的概率成功，期望是$0.5 \times 100=50$
另外，$0.5$的概率是年轻司机被查之后我们去找老司机帮忙，期望是$0.5\times (100+1000)=550$
那么最终期望就是$550+50=600$
【bzoj4318】$OSU!$——初步接触期望$dp$
题目大意
给定一个数列$S$，长度为$n$
给出$a_i$，$S_i$有$a_i$的概率是$1$，否则是$0$
如果得分是数列$S$中所有连在一起的$1$的长度的立方和，询问得分的期望
数据范围
$n\leqslant 100000,0\leqslant a_i\leqslant 1$
题解
设转移到$S_i$时，$S_1,S_2...S_i-1$中连在一起的$1$的最长后缀长度为$x$
易证，如果$S_i=0$，则贡献为$0$，如果$S_i=1$，则贡献为$(x+1)^3-x^3=3x^2+3x+1$
只需要考虑对答案有所影响的情况因此只要考虑，当$S_i=1$时，$x^2$和$x$的期望加起来，转移到$S_{i+1}$的期望即可
代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 100500
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
int n;
double f[maxn],dp[maxn],x1[maxn],x2[maxn];
int main(){
scanf("%d\n",&n);
For(i,1,n) scanf("%lf",&f[i]);
For(i,1,n){
x1[i]=(x1[i-1]+1)*f[i];
x2[i]=(x2[i-1]+2*x1[i-1]+1)*f[i];
dp[i]=dp[i-1]+(3*x2[i-1]+3*x1[i-1]+1)*f[i];
}
printf("%.1lf\n",dp[n]);
return 0;
}类似的题目可以参考不稳定的传送门
【bzoj1415】【noi2005】聪聪和可可——图论上的概率$dp$
题目大意
数据范围
保证无向图且无重边
$N,E\leqslant 1000$
题解
先进行$n$次$BFS$预处理出$p[i,j]$，表示聪聪在点$i$且可可在点$j$时，聪聪的最优策略第一步应去的点的编号(最短路)
由于聪聪被允许每次走两步，为了方便解题，我们把两步并作一步。聪聪为了吃掉可可，会这样移动$i\ \rightarrow\ p[p[i,j],j]$
而可可完全不知所措$♂$，每次会移动到点$j$的临近任意一个点$w$，或者乖乖$♂$站好，概率都是$\frac{1}{degree_j+1}$
弄清楚聪聪和可可应该会怎么转移，就可以得到所有的情况我们用$f[i,j]$表示聪聪在点$i$，可可在点$j$时聪聪抓住可可的平均步数
开始考虑边界条件当然，$f[i,i]=0$，因为聪聪和可可已经在同一个点。
若$p[p[i,j],j]=j\ or\ p[i,j]=j$时，则说明在这一步聪聪即可吃掉可可，那么$f[i,j]=1$
结合起来，得到图论上的概率dp的状态转移方程状态转移方程就是$$f[i,j]=\frac{\sum^{degree_j}f[p[p[i,j],j],w]+f[p[p[i,j],j],w]}{degree_j+1}+1$$
$Tips:$聪聪每次是走两步，因此在状态转移方程的最后还要加上$1$
程序
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define maxn 1050
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'&&ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m,c,k,et;
struct edge{int to,next;}e[2*maxn];
int last[maxn],dis[maxn][maxn];
int t[maxn],p[maxn][maxn];
double f[maxn][maxn];
inline void addedge(int u,int v){
e[++et]=(edge){v,last[u]};last[u]=et;
e[++et]=(edge){u,last[v]};last[v]=et;
t[u]++,t[v]++;
}
inline void bfs(int x){
queue <int> q;
q.push(x);dis[x][x]=0;
while (!q.empty()){
int h=q.front(),tmp=p[x][h];q.pop();
goedge(i,h)
if (dis[x][e[i].to]==-1||(dis[x][h]+1==dis[x][e[i].to]&&tmp<p[x][e[i].to])){
dis[x][e[i].to]=dis[x][h]+1;
if (!tmp) p[x][e[i].to]=e[i].to;
else p[x][e[i].to]=tmp;
q.push(e[i].to);
}
}
}
double dp(int x,int y){
if (f[x][y]) return f[x][y];
if (x==y) return f[x][y]=0;
if (p[x][y]==y||p[p[x][y]][y]==y) return f[x][y]=1;
double sum=dp(p[p[x][y]][y],y);
goedge(i,y) sum+=dp(p[p[x][y]][y],e[i].to);
return f[x][y]=sum/(t[y]+1)+1;
}
int main(){
n=read(),m=read();
c=read(),k=read();
For(i,1,m) addedge(read(),read());
memset(dis,-1,sizeof(dis));
For(i,1,n) bfs(i);
printf("%.3lf\n",dp(c,k));
return 0;
}感谢《浅析竞赛中一类数学期望问题的解决方法》对我的启发
【poj3744】Scout YYF I——矩阵乘法优化概率$dp$
题目大意
给出一个埋着$n$颗地雷的道路，起始在道路的起点$1$
给出概率$p$会往前走一步，否则走两步
也给出每颗地雷的位置，询问安全通过这条道路的概率（保留$7$位小数）
数据范围
$1\leqslant n\leqslant 10,0.25\leqslant p\leqslant 0.75$
地雷的位置在$[1,100000000]$之中
题解
$dp[i]$表示安全走到$i$点的概率，则有$dp[i]=p\times dp[i-1]+(1-p)\times dp[i-2]$
得出概率$DP$方程之后，发现这是类似于$Fibonacci$数列一样的常系数线性递推式，因此可以用矩阵乘法来优化概率$DP$，形式上来说就是
$$ \left[ \begin{matrix} p & p-1 \\ 1 & 0 \\ \end{matrix} \right] \times \left[ \begin{matrix} dp[i-1] & 0 \\ dp[i-2] & 0 \\ \end{matrix} \right] = \left[ \begin{matrix} dp[i] & 0 \\ dp[i-1] & 0 \\ \end{matrix} \right] $$
然后把整条道路分段，每段中只有一个地雷（计算时应使地雷在每一段的末尾），然后通过矩阵乘法优化概率$DP$递推得到在这一段中踩到地雷的概率$(K)$，也就得到安全通过这段道路的概率$(1-K)$，最后把安全通过每段道路的概率乘起来就是答案
程序
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,mine[20];
double a[3][3],ans[3][3];
double p,sum;
inline void mul(double a[3][3],double b[3][3],double result[3][3]){
double c[3][3];memset(c,0,sizeof(c));
For(i,1,2) For(j,1,2)
For(p,1,2) c[i][j]+=a[i][p]*b[p][j];
For(i,1,2) For(j,1,2) result[i][j]=c[i][j];
}
inline double count(int t){
a[1][1]=p,a[1][2]=1-p,a[2][1]=1,a[2][2]=0;
ans[1][1]=1,ans[1][2]=ans[2][1]=ans[2][2]=0;
while (t){
if (t&1) mul(ans,a,ans);
t>>=1;mul(a,a,a);
}
return ans[1][1];
}
int main(){
while (scanf("%d%lf",&n,&p)!=EOF){
For(i,1,n) mine[i]=read();
sort(mine+1,mine+n+1);
sum=1;
For(i,0,n-1) sum=sum*(1-count(mine[i+1]-mine[i]-1));
printf("%.7lf\n",sum);
}
return 0;
}如何用矩阵乘法优化常系数线性递推式
常系数线性递推式就是对于一个数列，满足递推关系：$A_n=C_1A_{n-1}+C_2A_{n-2}+…+C_kA_{n-k}+C_0$（其中$C_1,C_2…C_k,C_0$是常数）
因为矩阵乘法满足结合律，因此可以构造一个$(k+1)\times (k+1)$的矩阵，快速幂优化递推，形式上来说就是
$$ \left[ \begin{matrix} C_1 & C_2 & C_3 & \cdots & C_{k-2} & C_{k-1} & C_k & C_0 \\ 1 & 0 & 0 & \cdots & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & \cdots & 0 & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & 0 \\ 0 & 0 & 0 & \cdots & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & \cdots & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & \cdots & 0 & 0 & 0 & 1 \\ \end{matrix} \right] \times \left[ \begin{matrix} A_{n-1} \\ A_{n-2} \\ A_{n-3} \\ \vdots \\ A_{n-k+2} \\ A_{n-k+1} \\ A_{n-k} \\ 1 \\ \end{matrix} \right] = \left[ \begin{matrix} A_{n} \\ A_{n-1} \\ A_{n-2} \\ \vdots \\ A_{n-k+3} \\ A_{n-k+2} \\ A_{n-k+1} \\ 1 \\ \end{matrix} \right] $$
应用这个方法的题目还有：【poj3070】Fibonacci
鄂公网安备 42010202000505 号