[UVA] 10721 - Bar Codes

題目連結 → here


題意：

函數BC(n, k, m)為共有 n 個球，現在要分成 k 份，每份不超過 m 個。
然後要用64 bit整數儲存。

==================================================

我的作法：

遞迴方式實作，

BC(7, 4, 3) = 有 7 個球，分成 4 份，每份不超過 3 個，
而 BC(7, 4, 2) = 有 7 個球，分成 4 份，每份不超過 2 個。
有沒有發現呢！
其實每份不超過 3 個的解就是等於每份不超過 2 個的解 + 4份當中有 i 份有 3 個的解。
所以 BC(7, 4, 3) = BC(7, 4, 2)  + 其中1份有3個 + 其中2份有3個 + 其中3份有3個 + 4份都是3個。

• 其中1份有3個的算法 = BC(7-3, 4-1, 2) * C(4, 1)，
• 其中2份有3個的算法 = BC(7-3*2, 4-2, 2) * C(4, 2)，
• 其中3份有3個的算法 = BC(7-3*3, 4-3, 2) * C(4, 3)，
• 4份都是3個的算法 = BC(7-3*4, 4-4, 2) * C(4, 4)。

但需要注意的幾點是，
當 n <= 0 || k <= 0 || m <= 0時，BC(n, k, m) = 0;
當 n > k*m 或 n < k 時，BC(n, k, m) = 0;
當 n == k*m 或 k ==1 或 m == 1時， BC(n, k, m) = 1;

根據上面結論得到遞迴公式如下，
BC(n, k, m) = BC(n-i*m, k-i, m-1) * C(k, i);


小補充：
根據巴斯卡定理，
C(n, m) = C(n-1, m) + C(n-1, m-1)。

==================================================

程式碼：

/* 題目: UVa 10721 - Bar Codes

 * Language: C++

 * Created on: 2016年12月23日

 *   Author: hanting

 */

#include <iostream>

#include <cstring>

using namespace std;

long long dp[55][55];

long long C(int n, int m)

{

    if(dp[n][m])

    {

        return dp[n][m];

    }

    else

    {

        if(n < m) return dp[n][m] = 0;

        if(m == 1) return dp[n][m] = n;

        if(m == 0) return dp[n][m] = 1;

        return dp[n][m] = C(n-1, m) + C(n-1, m-1);

    }

}

long long dpBC[51][51][51];

long long BC(int n, int k, int m)

{

    if(n <= 0 || k <= 0 || m <= 0)

    {

        return 0;

    }

    if(dpBC[n][k][m])

    {

        return dpBC[n][k][m];

    }

    else

    {

        if(n < k || n > k*m) return 0;

        if(n == k*m || m == 1 || k == 1) return 1;

        long long tmp = 0;

        for(int i = 0; i*m < n; i++)

        {

            tmp += BC(n-i*m, k-i, m-1) * C(k, i);

        }

        return dpBC[n][k][m] = tmp;

    }

}

int main()

{

    memset(dp, 0, sizeof(dp));

    memset(dpBC, 0, sizeof(dpBC));

    int n, k, m;

    while(cin >> n >> k >> m)

    {

        cout << BC(n, k , m) << endl;

    }

    return 0;

}