首页 > 代码库 > HDOJ 4248 A Famous Stone Collector DP
HDOJ 4248 A Famous Stone Collector DP
DP: dp[i][j]前i堆排出j长度的序列有多少种排法,
dp[i][j]=dp[i-1][j] (不用第i堆),
dp[i][j]+=dp[i-1][j-k]*C[j][k] (用第i堆的k个石头)
A Famous Stone Collector
Time Limit: 30000/15000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 845 Accepted Submission(s): 322
Problem Description
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.
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.
Input
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.
available stones of each color respectively. All the input numbers will be nonnegative and no more than 100.
Output
For each test case, display a single line containing the case number and the number of different patterns Mr. B can make with these stones, modulo 1,000,000,007,
which is a prime number.
which is a prime number.
Sample Input
3 1 1 1 2 1 2
Sample Output
Case 1: 15 Case 2: 8HintIn 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.
Source
Fudan Local Programming Contest 2012
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long int LL; const LL MOD = 1000000007LL; LL C[11000][210]; void getC() { for(int i=0;i<11000;i++) C[i][0]=C[i][i]=1; for(int i=2;i<11000;i++) for(int j=1;j<i&&j<=200;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD; } LL dp[110][11000]; int n,a[110]; int main() { getC(); int cas=1; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) scanf("%d",a+i); memset(dp,0,sizeof(dp)); int len=0; dp[0][0]=1; for(int i=1;i<=n;i++) { len+=a[i]; for(int j=0;j<=len;j++) { dp[i][j]=(dp[i][j]+dp[i-1][j])%MOD; for(int k=1;k<=a[i]&&j-k>=0;k++) { dp[i][j]=(dp[i][j]+dp[i-1][j-k]*C[j][k])%MOD; } } } LL ans=0; for(int i=1;i<=len;i++) ans=(ans+dp[n][i])%MOD; printf("Case %d: %lld\n",cas++,ans%MOD); } return 0; }
HDOJ 4248 A Famous Stone Collector DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。