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;
}
View Code