Problem Solving►UVa

UVa 12034 - Race

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

特別注意可以並列。

Solution

dp[n][m]: 有幾種組合符合，n 是總共幾匹馬，m 是總共多少名次。
e.g.
dp[3][2] (3 匹馬，名次共有 2 名) = 6 => (13)2, 1(23), (23)1, 2(13), (12)3, 3(12)。 ()為並列
dp[4][1] = 1 => (1234)

情況一：名次只有 一名 時，當然就只有一種組合，就是全部人並列。

情況二： 兩名 以上時會等於：
在 [n-1][m-1] 的所有組合中，第 n 匹馬可以 插入 該組合中除了並列外的任一位置(* m)，這樣就可以讓名次多一了。
e.g. [4][3] 可以從 [3][2] 中得出: (13)2 => 4(13)2, (13)42, (13)24
加上
[n-1][m] 的所有組合中，第 n 匹馬可以去 並列 任意名次(* m)，而不會使總名次增加。
e.g. [4][3] 可以從 [3][3] 中得出: 123 => (41)23, 1(42)3, 12(43)

情況三：n 等於 m，沒有任何並列(其實也包含在情況二就是了)
[n-1][m] 就會等於零了。

1
2
3
4
5
6
dp[n][m] = 
{
    1:                             if m = 1.
    [n-1][m-1] * m + [n-1][m] * m: if m > 1.
    [n-1][m-1] * m + 0:            if n = m.                     
}

Code

UVa 12034
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#define MOD 10056
#define N 1001

int main()
{
    static int dp[N][N] = {}, ans[N];
    ans[1] = dp[1][1] = 1;
    for (int i = 2; i < N; ++i)
    {
        ans[i] = dp[i][1] = 1;

        for (int j = 2; j <= i; j++)
            ans[i] += dp[i][j] = ((dp[i - 1][j - 1] + dp[i - 1][j]) * j) % MOD;
        ans[i] %= MOD;
    }

    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; ++t)
    {
        int n;
        scanf("%d", &n);
        printf("Case %d: %d\n", t,ans[n]);
    }

    return 0;
}