比赛地址:http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=9193#overview
昀昀大神的blog:http://www.mzry1992.com/blog/miao/uestc-summer-team-training-2.html
D .A Famous Stone Collector [dp+组合计数]
给定n种颜色的石头,每种颜色有si颗,同种颜色的石头不区分。问能构成多少种不同的石头序列(不同的序列是指:1.石头数不同;2.石头数相同,至少一个位置的石头颜色不同)
dp[ i ][ j ]表示:考虑前i种石头构成的长度为j的序列的个数。
状态转移方程:
dp[ i ][ j ] = dp[ i-1 ][ j ]; //未放入第i种颜色的石头
for k := 1 ~ min( j , s[ i ] ) //放入k个第i种颜色的石头
dp[ i ][ j ] += dp[ i-1 ][ j - k ] * C[ j ][ k ];
其中C[ n ][ m ]表示组合数。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 //zzy2012.7.8AC 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<string> 6 #include<cmath> 7 #include<iostream> 8 #include<algorithm> 9 #include<map> 10 #include<vector> 11 #include<queue> 12 #define sf scanf 13 #define pf printf 14 #define pfn printf("\n"); 15 #define ll long long 16 #define INF 0x7fffffff 17 #define MOD 1000000007 18 19 using namespace std; 20 21 long long n,len,s[101],c[10001][101],dp[101][10001]; 22 23 void ini(){ 24 for(int i=0; i<=10000; i++) for(int j=0; j<=100; j++) c[i][j]=0; 25 c[0][0]=1; 26 for(int i=1; i<=10000; i++){ 27 c[i][0]=1; 28 for(int j=1; j<=100; j++) 29 c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD; 30 } 31 } 32 33 void DP(){ 34 long long t=s[1],m; 35 for(int i=1; i<=n; i++) 36 dp[i][0]=1; 37 for(int j=1; j<=s[1]; j++) 38 dp[1][j]=1; 39 for(int i=2; i<=n; i++){ 40 t+=s[i]; 41 for(int j=1; j<=t; j++){ 42 m=min((ll)j,s[i]); 43 dp[i][j]=dp[i-1][j]; 44 for(int k=1; k<=m; k++){ 45 dp[i][j]+=dp[i-1][j-k]*c[j][k]; 46 dp[i][j]%=MOD; 47 } 48 } 49 //dp[i][1]++; 50 } 51 } 52 53 int main() 54 { 55 long long num,cas=0; 56 ini(); 57 while(sf("%lld",&n)!=EOF){ 58 cas++; 59 len=0; 60 for(int i=1; i<=n; i++) {sf("%lld",s+i); len+=s[i];} 61 for(int i=0; i<=n; i++) for(int j=0; j<=len; j++) dp[i][j]=0; 62 DP(); 63 num=0; 64 //for(int i=1; i<=n; i++) 65 for(int j=1; j<=len; j++){ 66 num+=dp[n][j]; 67 num%=MOD; 68 } 69 pf("Case %lld: ",cas); 70 cout<<num<<endl; 71 } 72 return 0; 73 }
J .A Famous Game [概率题]
没理解的一道概率题,队友后来很神奇的过了,得到一个公式:
P = (Q+1) / (P+2);
L .The Famous Clock [签到题]
把罗马数字(I ~ XII)转换成阿拉伯数字(1 ~ 12)。