安排人在排隊（UVA - 10128）

Question

我想在弗吉尼亞在線評測解決問題Uva-10128 (Queue)。我無法找到解決此問題的方法。我搜索互聯網上，發現大部分的人已經通過使用DP precalulating解決了這個問題。

DP[1][1][1] = 1; 
for(N = 2; N <= 13; N++) 
    for(P = 1; P <= N; P++) 
     for(R = 1; R <= N; R++) 
      DP[N][P][R] = DP[N-1][P][R]*(N-2) + DP[N-1][P-1][R] + DP[N-1][P][R-1]; 

上面的代碼片段取自https://github.com/morris821028/UVa/blob/master/volume101/10128%20-%20Queue.cpp。

是否有人可以解釋上面的代碼中使用公式。

感謝

Answer 1

當你計算DP[N][P][R]你看最小的人的隊列中的位置。因爲他是最小的，他不能阻止任何人。但是如果他不站在隊列的任何一端，他將會被封鎖。

如果他是第一人，他是從行的開頭看到的隊列。因此，如果我們刪除他，隊列中包含N-1人，你只能看到P-1人從開始，但仍然從R人。因此有DP[N-1][P-1][R]組合。

如果他在中間，那麼通過刪除他，我們仍然可以看到P和R人。而且，由於存在中間N-2位置，有DP[N-1][P][R] * (N-2)組合。

如果他是排隊中的最後一個人，我們會得到DP[N-1][P][R-1]組合。推理與第一種情況相同。

因此DP[N][P][R]的組合總數是所有三種情況的總和。