Problem Solving►UVa

UVa 11420 - Chest of Drawers

Contents

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

Problem

題目網址
中文網址

Solution

dp[n][s][0]: n 個抽屜、s 個安全的、最上層 沒鎖 (0)
dp[n][s][1]: n 個抽屜、s 個安全的、最上層 有鎖 (1)

每次多一個的可能狀態：

(n-1, s)現在最上層是 鎖(L) 或 沒鎖(U) 的：
=> 再加一個 U 在上面
=> 再加一個 L 在上面

轉換如下所示：

1
2
3
4
5
6
7
8
dp[1][1][0] = 0
dp[1~n][0][1] = 0
dp[i][j][0] = 0 , if (j > i)
      
s  s-1 s+1 s+1
U   U   L   L | n
--------------|
U   L   U   L | n-1, s

Code

UVa 11420
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
#include <cstdio>

int main()
{
    int n, s;
    long long dp[66][67][2] = {}; //0: unlock, 1: lock

    dp[1][0][0] = 1;
    dp[1][1][1] = 1;

    for (int i = 2; i < 66; i++)
    {
        dp[i][0][0] = dp[i - 1][1][1] + dp[i - 1][0][0];
        for (int j = 1; j <= i; j++)
        {
            dp[i][j][0] = dp[i - 1][j + 1][1] + dp[i - 1][j][0];
            dp[i][j][1] = dp[i - 1][j - 1][1] + dp[i - 1][j - 1][0];
        }
    }

    while (scanf("%d%d", &n, &s) && (n >= 0 || s >= 0))    
        printf("%lld\n", dp[n][s][0] + dp[n][s][1]);    

    return 0;
}