首页 > ACM题库 > HDU-杭电 > HDU 4248-A Famous Stone Collector-动态规划-[解题报告]HOJ
2015
05-23

HDU 4248-A Famous Stone Collector-动态规划-[解题报告]HOJ

A Famous Stone Collector

问题描述 :

Mr. B loves to play with colorful stones. There are n colors of stones in his collection. Two stones with the same color are indistinguishable. Mr. B would like to
select some stones and arrange them in line to form a beautiful pattern. After several arrangements he finds it very hard for him to enumerate all the patterns. So he asks you to write a program to count the number of different possible patterns. Two patterns are considered different, if and only if they have different number of stones or have different colors on at least one position.

输入:

Each test case starts with a line containing an integer n indicating the kinds of stones Mr. B have. Following this is a line containing n integers – the number of
available stones of each color respectively. All the input numbers will be nonnegative and no more than 100.

输出:

Each test case starts with a line containing an integer n indicating the kinds of stones Mr. B have. Following this is a line containing n integers – the number of
available stones of each color respectively. All the input numbers will be nonnegative and no more than 100.

样例输入:

3
1 1 1
2
1 2

样例输出:

Case 1: 15
Case 2: 8

Hint
In the first case, suppose the colors of the stones Mr. B has are B, G and M, the different patterns Mr. B can form are: B; G; M; BG; BM; GM; GB; MB; MG; BGM; BMG; GBM; GMB; MBG; MGB.

题目大意:给n堆不同颜色的石头,给定每堆石子的数量,问,能够组成多少串满足:

Two patterns are considered different, if and only if they have different number of stones or have different colors on at least one position.

解题思路:开始的时候没有思路,想各种组合数学知识,最后,突发奇想,会不会是dp??对,就是dp

dp[i][j] 表示前i堆石子构成长度为j的串的方案数;

状态转移方程是:k为i堆使用的数量

dp[i][j] = (dp[i][j] + dp[i-1][j-k] * C[j][k]%M)%M;

ok问题解决,让我费了不少时间的是c[j][k](组合数)不是很好想。
code:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define M 1000000007
long long dp[110][10010];
long long C[11000][110];
void cc()
{
    int i,j;
    C[0][0]=1;
    for(i=1;i<10010;i++)
        for(j=0;j<=100;j++)
            if(j == 0) C[i][j] = C[i-1][j];
            else C[i][j] = (C[i-1][j]+C[i-1][j-1])%M;
            //C[i][j]=(j==0) ? C[i-1][j] : ();
}
int main()
{
    cc();
    int n;
    int cas = 1;
    while(cin >> n)
    {
        memset(dp,0,sizeof(dp));
        dp[0][0] = 1;
        int sum = 0;
        for(int i = 1;i <= n;i++)
        {
            int t;
            cin >> t;
            sum += t;
            for(int k = 0;k <= t;k++)
                for(int j = k;j <= sum;j++)
                    dp[i][j] = (dp[i][j] + dp[i-1][j-k] * C[j][k]%M)%M;
           
        }
        long long re = 0;
        for(int i = 1;i <= sum;i++) re = (re + dp[n][i])%M;
        cout << "Case " << cas++<< ": " << re << "\n";
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/wukonwukon/article/details/8160920