🔗 UVA-10721 Bar Codes

tags: `動態規劃(DP)`, `記憶化搜尋(Memoization)`

範例程式碼已於UVA、瘋狂程設(CPE) 上皆測試通過 (此題無 ZeroJudge )。

題意

條碼(bar code) 是由黑色和白色的 單元(unit) 組成，且由黑色的單元開始，若干個 unit 可以組成一個 長條(bar) ，而若干個 bar 又能組成一個 bar code 。

給定三個整數 $n, k, m$ ，代表條碼的長度為 $n$ 個 unit 、具有 $k$ 個 bar 、每個 bar 的寬度最多為 $m$ 個 unit ，求有多少種不同的條碼可以滿足條件，即求 $BC(n, k, m)$ 。

思路：動態規劃(DP)

來自 @灵茶山艾府

求解 $BC(n, k, m)$ 時，我們可以考慮第一個 bar 的寬度 $x$ ，將問題分解成求解 $BC(n-x, k-1, m)$ 之子問題，也就是剩下 $n-x$ 個 units ， $k-1$ 個 bars ，每個 bars 最多 $m$ 個 units 時的答案。將這些子問題的答案加總即為 $BC(n, k, m)$ 的答案。

再來考慮 $x$ 的範圍，顯然 $x$ 不能超過目前可用的 unit 數量 $n$ ，且每個 bar 的寬度最多為 $m$ 個 units ，因此 $x$ 的範圍為 $[1, \min(n, m)]$ 。

由於每次的顏色必須和上次不同，且開頭也只能是黑色，因此在考慮每個子問題時，都只需當作只有一種顏色即可。

最後來寫邊界條件：

對於 $n=0$ 時，若 $k=0$ 代表能夠滿足條件，返回 $1$ ；否則代表 bar 的數量不夠，返回 $0$ 。
對於 $k=1$ 時，若 $n \leq m$ 代表能夠滿足條件，返回 $1$ ；否則代表 bar 的寬度超過限制，返回 $0$ 。

複雜度分析

時間複雜度： $O(N^3)$ $O (N^{3})$ ，其中 $N$ $N$ 為 $n$ $n$ 的最大值，對於每個詢問。
- 由於在同一個詢問中 $m$ 值固定，因此總共有 $O(N^2)$ 個子問題，求解每個子問題的時間複雜度為 $O(N)$ 。
- 由於 $k, m \leq n$ ，故考慮 $n$ 的最大值即可。
空間複雜度： $O(N^3)$ ，用於存儲子問題的答案。

使用 Top-Down 的方式實作動態規劃，並使用 functools.cache 進行記憶化搜尋(Memoization) 。

from functools import *

@cache
def BC(n, k, m):
    if n == 0: # 沒有unit了，若還有bar則不滿足
        return 1 if k == 0 else 0
    if k == 1: # 只有1個bar，若滿足限制條件則有1種可能
        return 1 if n <= m else 0
    res = 0
    for x in range(1, min(n, m)+1):
        res += BC(n-x, k-1, m) # 剩下n-x個units, k-1個bars, 每個bar最多還是m個units
    return res

while True:
    try:
        n, k, m = map(int, input().split())  
    except EOFError:
        break
    print(BC(n, k, m))

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 55;
#define endl '\n'

LL dp[N][N][N];

LL BC(int n, int k, int m) {
    if (dp[n][k][m] != -1) return dp[n][k][m]; // memoization
    if (n == 0) return k == 0; // 沒有unit了，若還有bar則不滿足
    if (k == 1) return n <= m; // 只有1個bar，若滿足限制條件則有1種可能
    LL res = 0;
    for (int x = 1; x <= min(n, m); ++x) {
        res += BC(n-x, k-1, m); // 剩下n-x個units, k-1個bars, 每個bar最多還是m個units
    }
    dp[n][k][m] = res;
    return res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, k, m;
    memset(dp, -1, sizeof(dp));
    while (cin >> n >> k >> m) {
        cout << BC(n, k, m) << endl;
    }
    return 0;
}