hdu 4248 A Famous Stone Collector(组合数学&DP)

A Famous Stone CollectorTime Limit: 30000/15000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 765    Accepted Submission(s): 286


Problem DescriptionInputOutputSample InputSample OutputSourceRecommend#include<algorithm>#include<iostream>#include<string.h>#include<sstream>#include<stdio.h>#include<math.h>#include<vector>#include<string>#include<queue>#include<set>#include<map>using namespace std;const int INF=0x3f3f3f3f;const int maxn=100010;const int mod=1000000007;int C[15000][150],num[150];__int64 dp[150][15000];//注意数组大小int main(){ int i,j,k,n,cas=1,sum,ans; for(i=0;i<=10010;i++)//注意组合数的范围 { C[i][0]=1; for(j=1;j<=i&&j<=105;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; } while(~scanf("%d",&n)) { for(i=1;i<=n;i++) scanf("%d",num+i); sum=0; memset(dp,0,sizeof dp); dp[0][0]=1; for(i=1;i<=n;i++) { sum+=num[i]; for(k=0;k<=num[i];k++)//由于利用上层结果。j,k嵌套顺序无关。 for(j=k;j<=sum;j++) dp[i][j]=(dp[i][j]+dp[i-1][j-k]*C[j][k])%mod; } ans=0; for(i=1;i<=sum;i++) ans=(ans+dp[n][i])%mod; printf("Case %d: %d\n",cas++,ans); } return 0;}