# 題目: 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
...以此類推

# 參考程式碼

# C++ code

#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;
}

# java code

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/

C++UVa DP