2011-05-29 07:48:40Morris
d898. Q10128: Queue
內容 ：
有 N 個人排成一列，每個人的身高都不一樣。當我們從前面看過去可以看到 P 個人，而當我們從後面看過去的時候可以看到 R 個人。這是因為他們的身高不一樣且彼此互相遮蓋的關係。請問這一列人共有多少種不同的排列方式有這樣有趣的特性。
輸入說明 ：
輸入的第一列有一個整數 T （1 <= T <= 10000）代表以下有多少組測試資料。
每組測試資料一列，含有 3 個整數 N（1 <= N <= 13）, P, R。請參考Sample Input。
輸出說明 ：
對每一組測試資料輸出共有多少種不同的排列方式，使得從前面看過去可以看到 P 個人，而從後面看過去的時候可以看到 R 個人。
範例輸入 ：
310 4 411 3 13 1 2
範例輸出 ：
9072010265761
提示 ：
※測資沒有問題，WA:line4540以上的話想想什麼樣的測資你的程式沒辦法處理
※ACM的測資就是這樣讓我吃了不少WA，別怪我= ="
出處 ：
UVa ACM 10128 (管理：david942j)
作法 : DP
我沒有辦法可以判定其他人為什麼寫那麼長，我也無從得知他們是怎麼寫的
開始說明
既然每個人都不一樣高，那麼我們設定新增的人比任何人都矮
就可以得到
DP[N][P][R] = DP[N-1][P][R]*(N-2) + DP[N-1][P-1][R] + DP[N-1][P][R-1];
DP[N-1][P][R]*(N-2) : 由於比任何人都矮，所以插在(N-1)人中，都不會被發現，所以*(N-2)(間隔)作法 : DP
我沒有辦法可以判定其他人為什麼寫那麼長，我也無從得知他們是怎麼寫的
開始說明
既然每個人都不一樣高，那麼我們設定新增的人比任何人都矮
就可以得到
DP[N][P][R] = DP[N-1][P][R]*(N-2) + DP[N-1][P-1][R] + DP[N-1][P][R-1];
DP[N-1][P-1][R] : 由於比任何人都矮，所以直接放在頭
DP[N-1][P][R-1] : 由於比任何人都矮，所以直接放在尾
為什麼這樣就可以了呢 ? 我分成兩個部分去做討論
看得到新增的人 & 看不到新增的人，再利用已知的條件，串起來得到
#include<stdio.h>
#include<string.h>
int main() {
int T, N, P, R;
long long DP[17][17][17];
memset(DP, 0, sizeof(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];
scanf("%d", &T);
while(T--) {
scanf("%d %d %d", &N, &P, &R);
printf("%lld\n", DP[N][P][R]);
}
return 0;
}