Problem Solving►UVa

UVa 10128 - Queue

Contents

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

Problem

中文網址

Solution

用DP，主要可以分成三種情況，將一個最矮的人放進:

  • 最前面，會使從前面能看到的人多一個， ans[n - 1][p - 1][r]
  • 最後面，會使從後面能看到的人多一個， ans[n - 1][p][r - 1]
  • n - 1 個人之間，有 n - 2 個位置， ans[n - 1][p][r] * (n - 2)

Code

UVa 10128
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>

int main()
{
    int Case, ans[14][14][14] = {};

    ans[1][1][1] = 1;
    for (int n = 2; n < 14; n++)
        for (int p = 1; p <= n; p++)
            for (int r = 1; r <= n; r++)
                ans[n][p][r] = ans[n - 1][p - 1][r] + ans[n - 1][p][r - 1] + ans[n - 1][p][r] * (n - 2);

    scanf("%d", &Case);
    while (Case--)
    {
        int N, P, R;
        scanf("%d%d%d", &N, &P, &R);        
        printf("%d\n", ans[N][P][R]);
    }

    return 0;
}