Организация людей в очереди (Ува - 10128)

Question

Я пытаюсь решить проблему Uva-10128 (Очередь) на UVa Online Judge. Я не могу найти способ подойти к этой проблеме. Я искал в интернете и обнаружил, что большинство людей решили эту проблему, предварительно вычислив 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] это сумма всех трех случаев.