摆花(2012Noip普及组第3题)

摆花

(flower.cpp/c/pas)

【问题描述】

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

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

【输入】

输入文件 flower.in,共 2 行。

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

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

【输出】

输出文件名为 flower.out。

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

【输入输出样例 1】

flower.in

2 4

3 2

flower.out

2

分析:

动态规划:

题目要求花必须按从小到大的顺序摆放,并且同种类的花必须挨着放,则题目就简单多了

a[i]表示第i种花最多使用的盆数
f[i][j]表示前i种花,摆j盆的摆放方案数。对于第i种花可以使用0、1、2...a[i]盆,对应的前i-1种花摆放的盆数为j-0、j-1、j-2、...j-a[i]
即f[i][j]=f[i-1][j]+f[i-1][j-1]+f[i-1][j-2]+...+f[i-1][j-a[i]] =f[i-1][j-k](0<=k<=a[i],j>=k)
方程写出来后,最关键的就是赋初始值

初始值f[1][0]=1,f[1][1]=1,...f[1][a[1]]=1;
初始值f[i][0]=1;(1<=i<=n)

2 4

3 2

为例:

很显然f[1][1]=f[1][2]=f[1][3]=1;

f[2][1]=2,前2种花,放一盆,则有1,2两种方法。又

f[2][1]=f[1][0]+f[1][1]=f[1][0]+1可以推出f[1][0]=1;

同样的方法可以推出f[2][0]=f[3][0]=...=f[n][0]=1;

(f[2][2]=f[1][0]+f[1][1]+f[1][2]

f[2][3]=f[1][1]+f[1][2]+f[1][3]

f[2][4]=f[1][2]+f[1][3]+f[1][2])

#include<iostream>
#include<cstring>
using namespace std;
int f[200][200]={{0,0}};
int a[200];
int main(){
 int n,m;
 cin>>n>>m;
 for(int i=1;i<=n;i++) cin>>a[i];
 memset(f,0,sizeof(f));
 for(int i=0;i<=a[1];i++) f[1][i]=1;
 for(int i=1;i<=n;i++)f[i][0]=1;
 for (int i=2;i<=n;i++)
  for(int j=1;j<=m;j++)
   for(int k=0;k<=a[i];k++)
    if (j>=k)f[i][j]=(f[i][j]+f[i-1][j-k])% 1000007;
 cout<<f[n][m]<<endl;
 return 0;
}

方法2:初始值f[0][0]=1;前0种花摆放0盆的方案数为1

//题目要求花必须按从小到大的顺序摆放,并且同种类的花必须挨着放,则题目就简单多了
//f[i][j]表示前i种花,摆j盆的摆放方案数。对于第i种花可以使用0、1、2...a[i]盆,对应的前i-1种花摆放的盆数为j-0、j-1、j-2、...j-a[i]
//即f[i][j]=f[i-1][j]+f[i-1][j-1]+f[i-1][j-2]+...+f[i-1][j-a[i]] (j>a[i])
//初始值f[0][0]=1;前0种花摆放0盆的方案数为1
//方程写出来后,最关键的就是赋初始值
#include<iostream>
#include<cstring>
using namespace std;
int f[200][200]={{0,0}};
int a[200];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    memset(f,0,sizeof(f));
    f[0][0]=1;
//    for(int i=0;i<=a[1];i++) f[1][i]=1;
//    for(int i=1;i<=n;i++)f[i][0]=1;
    for (int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=a[i];k++)
                if (j>=k)f[i][j]=(f[i][j]+f[i-1][j-k])% 1000007;
    cout<<f[n][m]<<endl;
    return 0;
}

       
       
时间: 08-20

摆花(2012Noip普及组第3题)的相关文章

守望者的逃离(2007年普及组第3题)| 贪心算法

守望者的逃离(2007年普及组第3题) [问题描述] 恶魔猎手尤迪安野心勃勃,他背叛了暗夜精灵,率深藏在海底的那加企图叛变,守望者在与尤迪安的交锋中遭遇了围杀.被困在一个荒芜的大岛上.为了杀死守望者,尤迪安开始对这个荒岛施咒,这座岛很快就会沉下去,到那时岛上的所有人都会遇难:守望者的跑步速度为17m/s, 以这样的速度是无法逃离荒岛的.庆幸的是守望者拥有闪烁法术,可在1s内移动60m,不过每次使用闪烁法术都会消耗魔法值10点.守望者的魔法值恢复的速度为4点/s,只有处在原地休息状态时才能恢复.

【基础练习】【卡特兰数】栈 2003年NOIP全国联赛普及组第三题 题解

卡特兰数,这是一向掌握不大熟练的内容,今天借NOIP2003普及组的第三题来总结一下.当然由于原题数据弱抱,不需要高精.如果有时间我会不断补充这篇文章里的内容. 二话不说上代码 //Catalan #include<iostream> using namespace std; long long n,f[20]={0}; /*NO.1 f[n+1]=f[i]*f[n-i]from 0 to n plus f[0]=1 int main(){ cin>>n; f[0]=1;f[1]=

Noip2012 普及组 第三题 摆花

博主声明: 新手第一次写动规的题解,如果出现错误请各位大力的喷,但不要骂脏话,最好告诉我怎么改,谢谢~.~ !!! 摆花 (flower.cpp/c/pas) [问题描述] 小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共 m 盆. 通过调查顾客的喜好,小明列出了顾客最喜欢的 n 种花,从 1 到 n 标号. 为了在门口展出更多种花,规定第 i 种花不能超过 ai 盆, 摆花时同一种花放在一起,且不同种类的花需按标号的从小到大的顺序依次摆列. 试编程计算,一共有多少种不同的摆花方案

【递归】Vijos P1132 求二叉树的先序序列(NOIP2001普及组第三题)

题目链接: https://vijos.org/p/1132 题目大意: 给定二叉树的中序和后序遍历,求该二叉树先序遍历. 题目思路: [递归] 这题妥妥递归. 二叉树先序根左右,中序左根右,后序左右根. 对于每一颗子树,它的后序最后一个必定是根,于是可以根据根在中序的位置把左子树和右子树区分开来. 1 // 2 //by coolxxx 3 // 4 #include<iostream> 5 #include<algorithm> 6 #include<string>

【基础练习】【字符串处理】noip2011普及组第2题 统计单词数题解

这又是一道成功加入"容易吗"系列的基础题= =原本很简单,可是我一开始太大意看错了题,以为是让输出该单词是第几个单词,实际上应该输出该单词的首字母在第几个位置:改过后只得了二十分,看了一组数据,原来第一个单词前面可以有前导空格--幸亏其他单词前没有,否则还真不知道怎么办:实现的时候又出了各种问题.于是我决定总结一下. 题目: 给定一个单词,请你输出它在给定的文章中出现的次数和第一次出现的位置.注意:匹配单词时,不区分大小写,但要求完全匹配,即给定单词必须与文章中的某一独立单词在不区分大

2002普及组第四题过河卒

题目描述 如图,A 点有一个过河卒,需要走到目标 B 点.卒行走规则:可以向下.或者向右.同时在棋盘上的任一点有一个对方的马(如上图的C点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点.例如上图 C 点上的马可以控制 9 个点(图中的P1,P2 - P8 和 C).卒不能通过对方马的控制点. 棋盘用坐标表示,A 点(0,0).B 点(n,m)(n,m 为不超过 20 的整数,并由键盘输入),同样马的位置坐标是需要给出的(约定: C<>A,同时C<>B).现在要求你计算出卒

C++ P1188 火星人(NOIP2004普及组第3题)

#include<iostream>#include<cstdio>using namespace std; int N[10005],n,m,time,ap[10005],sign[10005];//ap用来表示某一元素在排列中出现的次数: bool get,out;//表示是否已经找到标准排列,是否已经输出: void DFS(int x){ if(x>n) { get=1;//找到标准排列: time++; if(time==m+1) { for(int i=1;i&l

【递归】Vijos P1114 FBI树(NOIP2004普及组第三题)

题目链接: https://vijos.org/p/1114 题目大意: 把01串一分为二,左半边描述当前节点左子树,右半边描述右子树,子树全为1则为I节点,全为0则为B节点,混合则为F节点,直到当前串长度为1停止. 给定01串,求FBI树后序. 题目思路: [递归] 每次操作先操作左子树,再操作右子树,之后统计左右子树01状态,按照要求得到当前节点是 F B I中的哪一个. 由于输出后序,所以可以每次操作完左右子树后直接输出该节点,当前串长度为1则输出完返回. 1 // 2 //by cool

求全排列的数学方法(洛谷1088 火星人noip2004普及组第4题)

人类终于登上了火星的土地并且见到了神秘的火星人.人类和火星人都无法理解对方的语言,但是我们的科学家发明了一种用数字交流的方法.这种交流方法是这样的,首先,火星人把一个非常大的数字告诉人类科学家,科学家破解这个数字的含义后,再把一个很小的数字加到这个大数上面,把结果告诉火星人,作为人类的回答. 火星人用一种非常简单的方式来表示数字――掰手指.火星人只有一只手,但这只手上有成千上万的手指,这些手指排成一列,分别编号为1,2,3…….火星人的任意两根手指都能随意交换位置,他们就是通过这方法计数的. 一