這是一道2011年區域賽原題改編，難度頗高，雖然聽了雨巨的課但是還是沒做出來，看了題解后如夢方醒，遂寫此篇題解。
首先，我們可以設為吉吉囯國王在隊列長度為i的隊列中，處於j位置的狀態，從而可以推出狀態轉移方程如下：


方程（3）中因爲國王本不在隊列中，因此如果飯堂關門，國王也無法躋身與前k人中，因此無需增加p4.
預熱工作準備結束，下面進入正題。我們觀察方程（1），（2），（3）可知方程左右兩邊有相同項，從而我們可以對公式中加粗部分進行移項處理，從而可以得到新的方程組如下：

令：

我們通過觀察可以發現方程（2）和（3）中的是可以在循環過程中被直接求出的，因此我們可以將它當作常數來看待，我們令為常數項，從而可以得到


從而方程（2）的後兩項，方程（1）的最後一項與方程（3）的最後一項我們可以將其看作是常數來處理，進而我們可以推出一系列數列式：


現在我們所存在的問題是無法算出中的, 但是我們通過上面的數列可以發現，這件事是可以解決的，我們只需要將上面的式子往下面帶入，這樣就可以在最後一個式子中得到一個關於dp[i][i]的一元一次方程從而，就可以得出答案了。敲了那麽多累死了（：-）），直接上代碼了

#include<iostream>
#include<iomanip>
using namespace std;
double dp[2010][2010];
double c[2010]/*常數數組*/,p[2010]/*係數數組*/;
#define eps 1e-10

int main()
{
    int n,m,k;
    double p1,p2,p3,p4;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>k>>p1>>p2>>p3>>p4;
    if(p4<eps){
        cout<<"0.00000\n";
        return 0;
    }//此處是大坑，如果p4太小就直接返回0.
    double p12=p2/(1-p1);
    double p13=p3/(1-p1);
    double p14=p4/(1-p1);
    p[0]=1;//數列帶入時的係數數組
    for(int i=1;i<=n;i++){
        p[i]=p[i-1]*p12;
    }//計算的係數
    dp[1][1]=p4/(1-p1-p2);//dp[1][1]可直接算出
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(j<=k){
                c[j]=dp[i-1][j-1]*p13+p14;//算不同情況下的係數
            }
            else c[j]=dp[i-1][j-1]*p13;
        }
        double temp=0;
        for(int j=1;j<=i;j++){
            temp+=p[i-j]*c[j];
        }//數列帶入得到的係數
        dp[i][i]=temp/(1-p[i]);//計算得到dp[i][i]
        dp[i][1]=p12*dp[i][i]+p14;//計算dp[i][1]
        for(int j=2;j<i;j++){
            dp[i][j]=dp[i][j-1]*p12+c[j];
        }//帶入數列求出其他值
    }
    cout<<fixed<<setprecision(5)<<dp[n][m];
    return 0;
}