DP应该是肯定的,设 f [ i ] [ j ] 表示现在对*有 i 人,Tomato在第 j 个,我们可以很(简单的)艰难的列出下列方程:
f[i][1] = p1*f[i][1] + p2*f[i][i] + p4
f[i][j] = p1*f[i][j] + p2*f[i][j-1] + p3*f[i-1][j-1] + p4 (2<=j<=k)
f[i][j] = p1*f[i][j] + p2*f[i][j-1] + p3*f[i-1][j-1] (j>k)
(由于我们是在求第 i 项,所以第 i - 1 项是已知量)
然后化简可得:
令 a=p2/(1.0-p1) , b=p3/(1.0-p1) , c=p4/(1.0-p1)
f[i][1] = a*f[i][i] + c
f[i][j] = a*f[i][j-1] + b*f[i-1][j-1] + c (2<=j<=k)
f[i][j] = a*f[i][j-1] + b*f[i-1][j-1] (j>k)
再代入一(亿)下,可以求出 f [ i ] [ 1 ] 的表达式。
所以,我们先求出 [ i ] [ 1 ] ,然后就可以求出剩下的值了。
但是,这玩意怎么初始化呢?
YY一哈可以发现:
f[1][1] = a*f[1][1] + c = c / (1-a)
之后就水到渠成了。
最后YY一哈,有特判!有特判!有特判!(可能出现除数为 0 的情况)(调了一个晚上,~qwq~)(具体见Code)
Code:
#pragma GCC optimize(2) #pragma GCC optimize(3) #include<bits/stdc++.h> #define Zero(x) (((x)>0?(x):-(x))<1e-10) using namespace std; int n,m,K; double p1,p2,p3,p4,a,b,c,Inv[2005],f[2][2005]; int main() { while(scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&K,&p1,&p2,&p3,&p4)!=EOF) { if(Zero(p1+p2-1)==1) {printf("0.00000\n");continue;} p1=1.0-p1,a=p2/p1,b=p3/p1,c=p4/p1,Inv[0]=1; for(register int i=1;i<=n;++i) Inv[i]=Inv[i-1]*a; for(register int i=1;i<=n;++i) { f[i&1][1]=c; for(register int j=2;j<=min(i,K);++j) f[i&1][1]+=(b*f[(i-1)&1][j-1]+c)*Inv[i-j+1]; for(register int j=K+1;j<=i;++j) f[i&1][1]+=b*f[(i-1)&1][j-1]*Inv[i-j+1]; f[i&1][1]/=(1-Inv[i]); for(register int j=2;j<=min(i,K);++j) f[i&1][j]=a*f[i&1][j-1]+b*f[(i-1)&1][j-1]+c; for(register int j=K+1;j<=i;++j) f[i&1][j]=a*f[i&1][j-1]+b*f[(i-1)&1][j-1]; } printf("%.5lf\n",f[n&1][m]); } return 0; }