NOIP2012普及组第三题 摆花 TYVJ2069

diggersun

描述
   小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 m 盆。通过调 查顾客的喜好，小明列出了顾客最喜欢的 n 种花，从 1 到 n 标号。为了在门口展出更多种花， 规定第 i 种花不能超过 ai 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到 大的顺序依次摆列。
   试编程计算，一共有多少种不同的摆花方案。
输入格式
   第一行包含两个正整数 n 和 m，中间用一个空格隔开。
   第二行有 n 个整数，每两个整数之间用一个空格隔开，依次表示 a1、a2、……an。
输出格式
   输出只有一行，一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出 方案数对 1000007 取模的结果。
测试样例1
输入
   2 4
    3 2
输出
    2

备注
【输入输出样例说明】
          有 2 种摆花的方案，分别是(1，1，1，2)， (1，1，2，2)。括号里的 1 和 2 表示两种花，比如第一个方案是前三个位置摆第一种花，第四个位置摆第二种花。

【数据范围】

       对于 20%数据，有 0<n≤8，0<m≤8，0≤ai≤8； 对于 50%数据，有 0<n≤20，0<m≤20，0≤ai≤20；

       对于 100%数据，有 0<n≤100，0<m≤100，0≤ ai≤100。NOIP 2012

diggersun

非常好理解的dfs做法

1. #include <iostream>
   
2. using namespace std;
   
3. int a[100];
   
4. int c[100];
   
5. int n,m,i,s;
   
6. void dfs(int i)
   
7. {
   
8.     int j,k;
   
9.     if (i>=m)
   
10.     {
    
11.         s++;
    
12.         for (j=0; j<=m-1; j++) cout<<a[j];cout<<endl;
    
13.     }
    
14.     else for (k=((i==0)?0:a[i-1]); k<=n-1; k++)
    
15.             if (c[k]>0)
    
16.             {
    
17.                 a[i]=k;
    
18.                 c[k]--;
    
19.                 dfs(i+1);
    
20.                 c[k]++;
    
21.             }
    
22. 
    
23. }
    
24. int main()
    
25. {
    
26.     cin>>n>>m;
    
27.     for (i=0; i<=n-1; i++) cin>>c[i];
    
28.     dfs(0);cout<<s%1000007;
    
29.     return 0;
    
30. }
    
31. 
    

复制代码

diggersun

有点技巧的DP做法
其实这种简单的DP可以认为是递推，因为排列的顺序是由小到大的，那么用 a（x，y）表示第X个位置放上满了第Y种花，或者说Y种花摆满X个位置的所有可能情况，那么
a（x-1，y-1）就是y-1种花摆满x-1个位置，我们最后在x位置摆上第Y种花就可以得到 A（x y）
a（x-2，y-1）就是y-1种花摆满x-2个位置，我们最后在x-1和x位置摆上第Y种花就可以得到 A（x y） 当然第y种花要有2颗可以选择
****
然后累加。

1. #include <iostream>
   
2. #include <iomanip>
   
3. using namespace std;
   
4. int a[101][101];
   
5. int c[101];
   
6. int n,m,i,j,k,s;
   
7. int main()
   
8. {
   
9.     cin>>n>>m;
   
10.     for (i=1; i<=n; i++) cin>>c[i];
    
11.     //for (i=0; i<=n; i++) a[i][0]=1;
    
12.     a[0][0]=1;
    
13. 
    
14.     for (i=1; i<=n; i++)
    
15.         for (j=0; j<=m; j++)
    
16.             for (k=0; k<=c[i]; k++)
    
17.                 if (j-k>=0) a[j][i]=(a[j][i]+a[j-k][i-1]);
    
18. 
    
19.     for (i=0; i<=n; i++)
    
20.         {for (j=0; j<=m; j++) cout<<setw(3)<<a[j][i];
    
21.         cout<<endl;}
    
22. 
    
23. 
    
24.     cout<<a[m][n];
    
25.     return 0;
    
26. }
    
27. 
    

复制代码