思路：
分析题意，可以得到如下递推关系：
dp[i][j]表示i个人排队，Tomato在j位置的概率
j=1 时，dp[i][j] = p1*dp[i][j]+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 时，dp[i][j] = p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1];
令 p21=p2/(1-p1) ; p31=p3/(1-p1) ; p41=p4/(1-p1)
则整理得到：
j=1 , dp[i][j] = p21*dp[i][i]+p41;
2<=j<=k , dp[i][j] = p21*dp[i][j-1]+p31*dp[i-1][j-1]+p41;
k<j , dp[i][j] = p21*dp[i][j-1]+p31*dp[i-1][j-1].
由于在求dp[i][j]时，dp[i-1][j-1]已经求出故可以当作常数，则：
dp[i][j]=p21*dp[i][j-1]+c[j],(c[1]=p41)
迭代会发现形成了环，故只需将各式叠加
则有：dp[i][j] = (c[i]+p21*c[i-1]+p21^2*c[i-2]+……+p21^(i-1)*c[1])/(1-p21^i).
再就是要特判一下p4!!!
代码如下：
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<iomanip> 5 #include<cmath> 6 #include<cstring> 7 #include<vector> 8 #define ll __int64 9 #define pi acos(-1.0) 10 #define MAX 2005 11 using namespace std; 12 double dp[MAX][MAX],c[MAX]; 13 int main(){ 14 int n,m,k,i,j; 15 double p1,p2,p3,p4,p21,p31,p41,temp,p; 16 while(scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&k,&p1,&p2,&p3,&p4)!=EOF){ 17 if(p4<1e-8){ 18 printf("0.00000 "); 19 continue; 20 } 21 p21=p2/(1-p1); 22 p31=p3/(1-p1); 23 p41=p4/(1-p1); 24 dp[1][1]=p41/(1-p21); 25 c[1]=p41; 26 for(i=2;i<=n;i++){ 27 for(j=2;j<=i;j++){ 28 c[j]=p31*dp[i-1][j-1]; 29 if(j<=k) c[j]+=p41; 30 } 31 temp=1.0;p=0.0; 32 for(j=i;j>=1;j--){ 33 p+=temp*c[j]; 34 temp*=p21; 35 } 36 dp[i][i]=p/(1-temp); 37 dp[i][1]=p21*dp[i][i]+p41; 38 for(j=2;j<i;j++){ 39 dp[i][j]=p21*dp[i][j-1]+c[j]; 40 } 41 } 42 printf("%.5lf ",dp[n][m]); 43 } 44 return 0; 45 }