[Tmt514] Beverage Cup 2 D - A Parking Problem

contents

1. 1. Problem
2. 2. Sample Input
3. 3. Sample Output
4. 4. Solution

Problem

停車場有 n 個位置呈現單方向，由入口到出口分別編號為 1 到 n，現在有 m 名駕駛準備要停車，每名駕駛的停車方案都會先開到偏愛的車位上，如果發現已經有人停過，則會往後找一個空車位。由於駕駛入停車場任意順序。請問從 m 個駕駛中挑出 n 個駕駛，任意進入停車場，按照他們各自偏愛的停車方法，每一位都有停車位的合法選擇駕駛的方案數。

Sample Input

1
3
2 1 2

Sample Output

7

Solution

維護前 i 個位置中，挑選 j 名駕駛的方法數！dp[i][j] 表示前 i 個位置，挑選 j 個駕駛的方法數，並且滿足 j >= i，否則會有留空一格造成後續的非法解。窮舉下一個位置挑選的人數 k，得到 dp[i+1][j+k] += (dp[i][j] * C[A[i+1]][k])%MOD;

#include <stdio.h>

const int MOD = 1000000007;
const int MAXN = 64;
long long C[MAXN][MAXN] = {};
int main() {
    C[0][0] = 1;
    for (int i = 1; i < MAXN; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i-1][j] + C[i-1][j-1])%MOD;
    }
    int testcase, n;
    int A[MAXN];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        long long dp[MAXN][MAXN] = {};
        
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = i; j <= n; j++) {
                for (int k = 0; k <= A[i+1] && j+k <= n; k++) {
                    dp[i+1][j+k] += (dp[i][j] * C[A[i+1]][k])%MOD;
                    dp[i+1][j+k] %= MOD;
                }
            }
        }
        printf("%lld\n", dp[n][n]);
    }
    return 0;
}
/*
 1
 3
 2 1 2
*/