摆花   NOIP2012普及组

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共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

分析：

正解为：DP动态规划

此题重在考查对动态规划的理解和归纳，以及状态转移方程的递推

这道题还体现了01背包的概念

问题分析：

这是一个典型DP题

理解这道题时发现有几个特征：

1.子问题重叠性质：  总是在解决第i种花摆几盆的问题

    整个摆花的过程为：第一种花摆几盆，第二种花摆几盆…..,第n种花摆几盆；

   其实我们在解决一个问题，就是第i种花摆几盆的问题. 整个问题分解为一个相似的

   子问题，就是第i种花摆几盆的问题.

2. 最优子结构性质:  最终有几种不同的摆花方案，取决于第i种花摆几盆；

    第一种花摆几盆，第二种花摆几盆….,一直到第n种花摆几盆组成一种方案；

    每次每种花不同的摆放盆数，组合起来，就是总共的摆花方案数.

    因为总盆数不能大于m,所以每次第i种花摆几盆，取决于前 i-1种花摆放的总盆数；

   第i种花的状态总是由i-1的状态转移而来.

    基于以上分析，我们得出这是一道DP动态规划题；根据题意描述也是一道01背包题

解题思路：

我们用两种方法来做这道题

1.   DP动态规划

2.  01背包

首先用DP动态规划的方法：

1.首先要确定子问题

2.确定状态和状态变量

3.确定决策并写出状态转移方程

4.寻找边界条件

子问题就是第i种花摆k盆的问题（0<=k<=ai）;

用f[i][j] 这种状态表示前i种花，总数摆了j盆的 方案数

于是得到状态转移方程： f[ i ][ j ]=f[i][j] + f[i-1][j-k]

状态转移方程的解释：

f[i][j] ：表示前i种花，总数摆了j盆的 方案数

K:  表示第i种花摆放k盆

f[i-1][j-k] ：表示前i-1种花总数摆了j-k盆的方案数

释义：前i种花总数摆了j盆，第i种花摆了k盆； 那么前i-1种花总数就摆了j-k盆

最后结果要 mod 1000007

代码设定：

i: 表示第i种花

j: 表示前i种花总的摆放盆数

K:  表示第i种花摆放了k盆

a[i]： 表示第i种花最大可以摆a[i]盆

f[n][m]：摆放n种，总数m盆花的方案数

f[0][0]=1: 一盆花都不摆也是一种方案

#include<iostream> using namespace std; const int maxn=108, mod = 1000007; int n, m, a[maxn], f[maxn][maxn]; // n种花总数m盆，a[]每种花最多可摆盆数，f[]存方案数 int main() { cin>>n>>m; memset(f,0,sizeof(f)); f[0][0] = 1; //一盆花也不摆也是一种方案 for(int i=1; i<=n; i++) //n种花 { cin>>a[i]; for(int j=0; j<=m; j++) //总数m盆花 { for(int k=0; k<=min(j, a[i]); k++) //这种花摆几盆 { f[i][j] = (f[i][j] + f[i-1][j-k])%mod; //状态转移方程 每次都要mod,防止溢出 } } } cout<<f[n][m]%mod<<endl; return 0; }

下一篇讲用01背包的方法AC这道题

扫码标进群，进群学习