內容 :
有 N 個人排成一列,每個人的身高都不一樣。當我們從前面看過去可以看到 P 個人,而當我們從後面看過去的時候可以看到 R 個人。這是因為他們的身高不一樣且彼此互相遮蓋的關係。請問這一列人共有多少種不同的排列方式有這樣有趣的特性。
輸入說明 :
輸入的第一列有一個整數 T (1 <= T <= 10000)代表以下有多少組測試資料。
每組測試資料一列,含有 3 個整數 N(1 <= N <= 13), P, R。請參考Sample Input。
輸出說明 :
對每一組測試資料輸出共有多少種不同的排列方式,使得從前面看過去可以看到 P 個人,而從後面看過去的時候可以看到 R 個人。
範例輸入 :
3
10 4 4
11 3 1
3 1 2
範例輸出 :
90720
1026576
1
提示 :
※測資沒有問題,WA:line4540以上的話想想什麼樣的測資你的程式沒辦法處理
※ACM的測資就是這樣讓我吃了不少WA,別怪我= ="
出處 :
UVa ACM 10128 (管理:david942j)
解題策略
DP
假設新增使用者最矮,若最矮的可以插入a[n-1][p][r]的n-1人中間的任何位置,位置有(n-2)個,a[n-1][p][r]*(n-2);
若最矮的人排在最前面則為a[n-1][p-1][r];若最矮的人排在最後面則為a[n-1][p][r-1]
所以a[n][p][r]=a[n-1][p][r]*(n-2)+a[n-1][p-1][r]+a[n-1][p][r-1]