noip2012摆花

NOIP2012 的 “摆花” 问题是一道经典的动态规划题目，以下是对该题目的详细分析：

题目描述

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 种花，从 到 标号。为了在门口摆上好看的花，小明规定第 种花不能超过 盆，摆花时同一种花放在一起，且不同种类的花需按标号从小到大的顺序依次摆列。试编程计算，一共有多少种不同的摆花方案。

输入格式

第一行包含两个正整数 和 ，表示花的种类数和要摆的花盆数。第二行包含 个整数，第 个数 表示第 种花最多能摆的盆数。

输出格式

输出一个整数，表示不同的摆花方案数。由于方案数可能很大，输出对 取模的结果。

样例输入收起plaintext2 4

3 2

样例输出收起plaintext2

数据范围

对于 的数据，有 ；对于 的数据，有 ；对于 的数据，有 。

解题思路

本题可以使用动态规划来解决。定义状态 表示用前 种花摆 盆花的方案数。

初始化时，，表示不使用任何花摆 盆花有一种方案，即什么都不摆。

状态转移方程为：，表示用前 种花摆 盆花的方案数，是由用前 种花摆 盆花的方案数累加得到的，其中 表示第 种花使用的盆数，取值范围是从 到 ，即不能超过当前要摆的盆数 和第 种花最多能摆的盆数 。

最后答案为 ，即使用前 种花摆 盆花的方案数。

代码实现（C++）收起cpp#include <iostream>

#include <cstring>

using namespace std;

const int MAXN = 105;

const int MOD = 1000007;

int dp[MAXN][MAXN];

int a[MAXN];

int main() {

int n, m;

cin >> n >> m;

for (int i = 1; i <= n; i++) {

cin >> a[i];

}

// 初始化

dp[0][0] = 1;

// 动态规划计算方案数

for (int i = 1; i <= n; i++) {

for (int j = 0; j <= m; j++) {

for (int k = 0; k <= min(j, a[i]); k++) {

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

}

}

}

cout << dp[n][m] << endl;

return 0;

}

时间复杂度：，其中 是花的种类数， 是要摆的花盆数。空间复杂度：，可以通过滚动数组优化到 。