UVA 10128 - Queue

included in 作業筆記演算法 UVA C++

2019-04-06 133 words One minute

Contents

本題為中山大學高等程式設計課程作業指定題目之四星題。

題目大意

有 N 個人排隊，求往前看可以看到 P 個人、且往後看可以看到 R 個人的組合數。

輸入範圍

1 <= N <= 13

解法

假設 dp[i][j][k] 代表在有 i 個人時，往前看可以看到 j 個人且往後看可以看到 k 個人的組合數

考慮 dp[1][1][1] 為 1

假設現在都是從高到低進來排隊，則當進來下一個人時，考慮三種情況：

排前面，後面的人往前看可以多看到一個人
排後面，前面的人往後看可以多看到一個人
排中間，n 個位置不含頭尾會有 n - 1 個空缺，所以有 i - 1 種可能

得到這個結論後，可以直接三層 for 初始化陣列，輸入後直接拿值就好。

要注意的是，我實作 dp 的部分是用 i - 1 去想，所以情況 3 會是 i - 1 人有 i - 2 種可能！

程式碼

        
        
        
    
#include <iostream>
using namespace std;
int dp[15][15][15];
int main(int argc, char *argv[]) {
    dp[1][1][1] = 1;
    for(int i=2; i<=13; i++) {
        for(int j=1; j<=i; j++) {
            for(int k=1; k<=i; k++) {
                dp[i][j][k] = dp[i-1][j-1][k] + dp[i-1][j][k-1] + dp[i-1][j][k] * (i-2);
            }
        }
    }
    int T;
    cin >> T;
    while(T--) {
        int n, p, r;
        cin >> n >> p >> r;
        cout << dp[n][p][r] << endl;
    }
    return 0;
}