UVA-10721 - Bar Codes

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！
• 本題選為「20161220 大學程式能力檢定 CPE」題目。
• 相同題目：NCTU-11187

題意概要

題目給定 $n$ 個連續排列的長條形條碼 (Bar code)，條碼可為黑色或或白色，顏色相同且相鄰的條碼視為一個部分； 試球：將 $n$ 個條碼分成 $k$ 個部分，且每個部分都不超過 $m$ 的分法數。

• 分析：本題為動態規劃 (Dynamic Programming; DP) 的簡單題型。我們可以定義一個函式 $f(i, j, p)$ 為$i$ 個條碼分成 $j$ 個部分，且每個部分的長度不超過 $p$ 的方法數。故此函式可以寫成如下：

  $\begin{align*} f(i, j, p) = \sum_{i = 1}^{i = n}{ \sum_{j = 1}^{j = k}{ \sum_{p = 1}^{p = m}}{ f(i - p, j - 1, p) } } \end{align*}$

  • 此題要記得使用 long long int。

Input

Each input will contain three positive integers $n$, $k$, and $m$ ($1 \le n, k, m \le 50$).

Output

For each input print the total number of symbols in $BC(n, k, m)$. Output will fit in $64$-bit signed integer.

Sample Input

7 4 3
7 4 2

Sample Output

16
4