# 題目: UVa 10721 - Bar Codes

# 題目說明

bar-code 是由黑色及白色線條組成的，相鄰所有同顏色的線條視為一個區域
有一個算法 BC(N, K, M) ，代表總共有 N 條線， K 個區域，每個區域最多有 M 條線
給一組 (N, K, M) ，求此情況的排列數

INPUT:
每筆測資輸入 3 個整數 N 、 K 、 M

OUTPUT:
輸出 BC(N, K, M)

先將所有情況的答案算出儲存，再根據 N, K, M 的值輸出答案

0 條線、0 個區域必定只有一種可能，將所有 bc[0][0][i] 設為 1
利用 3 層 for 迴圈動態規劃，對於 bc[i][j][k] 來說，為 bc[i - x][j - 1][k] 的總和 (x 為 1 ~ min (i, k))

當 j與i 多 1 時，必定是在最後加上一個不同顏色的線條
例如題目裡的 bc[7][4][3] 的答案為 16
是 bc[6][3][3] 、 bc[5][3][3] 、 bc[4][3][3] 的加總， 7 + 6 + 3 = 16
... 以此類推

	#include <iostream>
	#include <memory.h>

	using namespace std;

	int main()
	{
	// fast io
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, k, m;
	long long bc[51][51][51];

	for (int i = 0; i < 51; ++i) bc[0][0][i] = 1;

	for (int i = 1; i < 51; ++i) for (int j = 1; j < 51; ++j) for (int k = 1; k < 51; ++k)
	for (int x = 1; x <= i && x <= k; ++x) bc[i][j][k] += bc[i - x][j - 1][k];

	while (cin >> n >> k >> m) cout << bc[n][k][m] << "\n";

	return 0;
	}

	import java.util.Scanner;

	class Main
	{
	public static void main(String[] args)
	{
	Scanner sc = new Scanner(System.in);
	long bc[][][] = new long[51][51][51];

	for (int i = 0; i < 51; ++i) bc[0][0][i] = 1;

	for (int i = 1; i < 51; ++i) for (int j = 1; j < 51; ++j) for (int k = 1; k < 51; ++k)
	for (int x = 1; x <= i && x <= k; ++x) bc[i][j][k] += bc[i - x][j - 1][k];

	int n, k, m;
	while (sc.hasNextInt())
	{
	n = sc.nextInt();
	k = sc.nextInt();
	m = sc.nextInt();
	System.out.println(bc[n][k][m]);
	}
	}
	}

https://blog.csdn.net/mobius_strip/article/details/45092387
https://summon528.github.io/2017/12/13/UVA-10721-Bar-Codes/