概率，$dp$。
设$dp[i][j]$表示有$i$个人在排队，$Tomato$排在第$j$个的情况下，到达目标状态的概率。$dp[n][m]$为答案。
当$j=1$时，$dp[i][1]=p1*dp[i][1]+p2*dp[i][i]+p4$；
当$2<=j<=k$时，$dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]+p4$；
当$k<j<=i$时，$dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]$。
将上面三个式子第一项往左移，左右同除以左边系数之后，得到：
当$j=1$时，$dp[i][1]=A*dp[i][i]+C$；
当$2<=j<=k$时，$dp[i][j]=A*dp[i][j-1]+B*dp[i-1][j-1]+C$；
当$k<j<=i$时，$dp[i][j]=A*dp[i][j-1]+B*dp[i-1][j-1]$。
其中$A=p2/(1-p1)$，$B=p3/(1-p1)$，$C=p4/(1-p1)$。
加下来就是要把这个东西算出来。又是一顿骚操作。
再写的简单一点吧：
当$j=1$时，$dp[i][1]=A*dp[i][i]+x[j]$，此时$x[j]=C$；
当$2<=j<=k$时，$dp[i][j]=A*dp[i][j-1]+x[j]$，此时$x[j]=B*dp[i-1][j-1]+C$；
当$k<j<=i$时，$dp[i][j]=A*dp[i][j-1]+x[j]$，此时$x[j]=B*dp[i-1][j-1]$；
$x[j]$可以通过$dp[i-1][....]$直接算出来。
假设现在我们需要计算$dp[4][1]$至$dp[4][4]$，我们分别设$dp[4][1]$至$dp[4][4]$为$a$,$b$,$c$,$d$。
得到四个等式：
$a=A*d+x[1]$ ①
$b=A*a+x[2]$ ②
$c=A*b+x[3]$ ③
$d=A*c+x[4]$ ④
将②代入③，再将新得到的③代入④，再将新得到的④代入①，
得到：$a=A^4*a+A^3*x[2]+A^2*x[3]+A^1*x[4]+A^0*x[1]$ ⑤，就可以求出$a$了，即求出了$dp[4][1]$。
⑤式子的得到是有规律的，自己写一遍就知道了。得到了$dp[4][1]$就可以知道$dp[4][2..4]$了。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-6; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } template <class T> inline void read(T &x) { char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } } int n,m,k; double p1,p2,p3,p4,A,B,C; double dp[2][2005],x[2005]; double powA[2005]; int main() { while(~scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&k,&p1,&p2,&p3,&p4)) { if(p4<eps) { printf("0.00000 "); continue; } A=p2/(1-p1); B=p3/(1-p1); C=p4/(1-p1); powA[0]=1; for(int i=1;i<=n;i++) powA[i]=powA[i-1]*A; int flag=0; dp[flag][1]=C/(1-A); flag=1; for(int i=2;i<=n;i++) { for(int j=1;j<=i;j++) { if(j==1) x[j]=C; else if(j>=2&&j<=k) x[j]=B*dp[flag^1][j-1]+C; else x[j]=B*dp[flag^1][j-1]; } double sum=0; for(int j=2;j<=i;j++) sum=sum+x[j]*powA[i+1-j]; sum=sum+x[1]*powA[0]; dp[flag][1]=sum/(1-powA[i]); for(int j=2;j<=i;j++) dp[flag][j]=A*dp[flag][j-1]+x[j]; flag=flag^1; } printf("%.5f ",dp[flag^1][m]); } return 0; }