P1077 摆花

2018-06-17 22:26:38来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共m盆。通过调查顾客的喜好,小明列出了顾客最喜欢的n种花,从1到n标号。为了在门口展出更多种花,规定第i种花不能超过ai盆,摆花时同一种花放在一起,且不同种类的花需按标号的从小到大的顺序依次摆列。

试编程计算,一共有多少种不同的摆花方案。

输入输出格式

输入格式:

第一行包含两个正整数n和m,中间用一个空格隔开。

第二行有n个整数,每两个整数之间用一个空格隔开,依次表示a1、a2、……an。

输出格式:

输出只有一行,一个整数,表示有多少种方案。注意:因为方案数可能很多,请输出方案数对1000007取模的结果。

输入输出样例

输入样例#1:
2 4
3 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 普及组 第三题

用dp[i][j]表示前i种花,放了j朵的方案数

然后枚举可以已经放置的花的数量k就可以

转移方程:

  dp[i][j]+=(dp[i-1][k])%1000007

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=101;
 7 int read(int & n)
 8 {
 9     char p='+';int x=0;
10     while(p<'0'||p>'9')
11         p=getchar();
12     while(p>='0'&&p<='9')
13     x=x*10+p-48,p=getchar();
14     n=x;
15 }
16 int n,m;
17 int dp[MAXN][MAXN];
18 int num[MAXN];
19 int main()
20 {
21     read(n);read(m);
22     for(int i=1;i<=n;i++)
23         read(num[i]),dp[i][0]=1;
24     dp[0][0]=1;
25     for(int i=1;i<=n;i++)// 每一种花 
26     {
27         for(int j=1;j<=m;j++) 
28         {
29             for(int k=j;k>=j-num[i]&&k>=0;k--)
30             {
31                 dp[i][j]+=(dp[i-1][k])%1000007;
32             }
33         }
34     }
35     cout<<dp[n][m]%1000007;
36     return 0;
37 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:浅谈引用类型

下一篇:3122 奶牛代理商 VIII