安排人在排队（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]的组合总数是所有三种情况的总和。