Fudan University Local Contest 2012 [7月8日暑假集训]

比赛地址：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 ]表示组合数。

View Code

 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）。