安排人员排队 (Uva - 10128)

Question

我正在尝试解决 UVa Online Judge 上的问题 Uva-10128 (Queue)。我找不到解决这个问题的方法。我在网上搜索了一下，发现大部分人都是通过使用DP进行预计算来解决这个问题的。

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]的组合总数是所有三种情况的总和。

安排人员排队 (Uva - 10128)

Arranging people in queue (Uva - 10128)

dynamic-programming

backtracking