【期望DP】[UVA1498] Activation

太过爱你忘了你带给我的痛 2023-06-01 06:09 15阅读 0赞

显然是概率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 }

转载于:https://www.cnblogs.com/zhenglw/p/11299699.html