【期望DP】[UVA1498] Activation-蒲公英云

【期望DP】[UVA1498] Activation

显然是概率DP

我们用dp[i][j]表示队伍中有i个人，lyk的小迷妹现在排在j这个位置时的概率大小

不难列出下列转移方程：

（显然已经排到前面k个位置的时候是要加上爆炸也就是p4的概率的）

f[i][1]=f[i][1]*p1+f[i][i]*p2+p4
f[i][j]=f[i][j]*p1+f[i][j-1]*p2+f[i-1][j-1]*p3+p4(j∈[2,k])
f[i][j]=f[i][j]*p1+f[i][j-1]*p2+f[i-1][j-1]*p3(j∈[k+1,i])

这是一个从前往后递推的过程，但是十分不和谐的是：f[i][1]的递推式中出现了$f[i][i]$,显然我们要想办法把这玩意儿给消掉

先化简，把两边同类项合并了，结果是这样的：

f[i][1]=f[i][i]*\frac{p2}{1-p1}+\frac{p4}{1-p1}
f[i][j]=f[i][j-1]*\frac{p2}{1-p1}+f[i-1][j-1]*\frac{p3}{1-p1}+\frac{p4}{1-p1}(j∈[2,k])
f[i][j]=f[i][j-1]*\frac{p2}{1-p1}+f[i-1][j-1]*\frac{p3}{1-p1}(j∈[k+1,i])

由于从前往后递推，在求f[i][j]是，f[i-1][]的所有值我们已经求出来了，所以可以看做常数,p1,p2,p3,p4显然已知，也是常数

所以我们可以把这玩意为当做方程解，我们只要把f[i][i]看做未知数，在不断的迭代下去即可

大概是这个样子：

不妨令a=$\frac{p2}{1-p1}$,$b=\frac{p3}{1-p1}$,$c=\frac{p4}{1-p1}$

设$C_j=f[i-1][j-1]*c+d$

则有：f[i][1]=f[i][i]*a+c
f[i][2]=f[i][1]*a+C_2
(然后把f[i][1]代入②式，依次类推……)

最后我们把式子最后面的常数部分设成sol

显然可以得到f[i][i]=a^{i}*f[i][i]+sol

也就是说
f[i][i]=\frac{sol}{1-a^i}

这样填完所有$f[][]$的表之后这道题也就解决了qaq

不过因为空间限制，我们要压掉f[][]第一维(f[i][]的值只与f[i-1][]有关)

代码实现在这里哦~

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 inline int read(){
 4     int ans=0,f=1;char chr=getchar();
 5     while(!isdigit(chr)){
     if(chr=='-')f=-1;chr=getchar();}
 6     while(isdigit(chr)) {ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
 7     return ans*f;
 8 }const int M = 2005;int n,m,k;
 9 double f[2][M],p1,p2,p3,p4,a,b,c,v[M],p[M];
10 int main(){
11     while(~scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&k,&p1,&p2,&p3,&p4)){
12         if(fabs(p4)<=1e-5) {puts("0.00000");continue;}//p4为0时显然不可能
13         a=p2/(1-p1),b=p3/(1-p1),c=p4/(1-p1);
14         v[0]=1;for(int i=1;i<=n;i++) v[i]=v[i-1]*a;//预处理a的i次方
15         p[1]=c;f[1][1]=p4/(1-p1-p2);
16         for(int i=2;i<=n;i++){
17             double sol=0;
18             for(int j=2;j<=k;j++) p[j]=f[i-1&1][j-1]*b+c;
19             for(int j=k+1;j<=i;j++) p[j]=f[i-1&1][j-1]*b;//求每一个方程式的常数项
20             for(int j=1;j<=i;j++) sol+=v[i-j]*p[j];//求最后一个式子f[i][i]=......的常数项
21             f[i&1][i]=sol/(1-v[i]);
22             f[i&1][1]=f[i&1][i]*a+c;//回代消元
23             for(int j=2;j<i;j++) f[i&1][j]=f[i&1][j-1]*a+p[j];//回去填表
24         }printf("%.5lf\n",f[n&1][m]);
25     }
26     return 0;
27 }