Organisation de personnes en file d'attente (Uva - 10128)

Question

J'essaie de résoudre le problème Uva-10128 (Queue) sur UVa Online Judge. Je ne suis pas en mesure de trouver un moyen d'aborder ce problème. J'ai cherché sur Internet et j'ai constaté que la plupart des gens ont résolu ce problème en précalculant l'utilisation de 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]; 

Au-dessus de l'extrait de code est pris de https://github.com/morris821028/UVa/blob/master/volume101/10128%20-%20Queue.cpp. Est-ce que quelqu'un peut expliquer la formule utilisée dans le code ci-dessus?

Merci

Answer 1

Lorsque vous calculez DP[N][P][R] vous regardez la position de la personne la plus petite dans la file d'attente. Parce qu'il est le plus petit, il ne peut bloquer personne. Mais il sera bloqué s'il ne se trouve pas à la fin de la file d'attente.

S'il est la première personne dans la file d'attente, il est vu depuis le début de la ligne. Donc, si nous l'enlevons, la file d'attente contient N-1 personnes et vous pouvez seulement voir P-1 personnes depuis le début, mais toujours R personnes de la fin. Par conséquent, il existe DP[N-1][P-1][R] combinaisons.

S'il est au milieu, alors en le retirant nous pouvons toujours voir P et R personnes. Et puisqu'il y a N-2 positions au milieu, il y a DP[N-1][P][R] * (N-2) combinaisons.

Et s'il est la dernière personne dans la file d'attente, nous obtenons DP[N-1][P][R-1] combinaisons. Le raisonnement est identique au premier cas.

Donc le nombre total de combinaisons pour DP[N][P][R] est la somme des trois cas.