P1077 [NOIP 2012 普及组] 摆花

题目描述

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

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

输入格式

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

第二行有 $n$ 个整数，每两个整数之间用一个空格隔开，依次表示 $a_1,a_2,\cdots ,a_n$。

输出格式

一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 $10^6+7$ 取模的结果。

输入输出样例 #1

输入 #1

2 4
3 2

输出 #1

2

说明/提示

【数据范围】

对于 $20\%$ 数据，有 $0<n\le 8,0<m\le 8,0\le a_i\le 8$。

对于 $50\%$ 数据，有 $0<n\le 20,0<m\le 20,0\le a_i\le 20$。

对于 $100\%$ 数据，有 $0<n\le 100,0<m\le 100,0\le a_i\le 100$。

NOIP 2012 普及组 第三题

solution

动态规划

• 1 定义公式

•  dp[i][j]: 用前 i 种花摆出 j 盆的方案数量
  

• 2 递推关系
  • dp[i][j] += dp[i][j - k] // 用k个第i种花
• 3 结果
  • dp[n][m]

实际dp可以省略第一个维度，但是要注意更改顺序，防止连锁反应

代码

#include <vector>
#include "set"
#include "iostream"
#include "unordered_map"
#include "algorithm"
#include "cstring"
#include "cmath"
#include "iomanip"
#include "cstdio"

/*
 * P1077 [NOIP 2012 普及组] 摆花
 * 题目大意：n种花，每种a[i]盆,摆出m盆,要求同一种花摆在一起,种类按照从小到大的顺序选择，共有多少种摆法
 * 0<n,m,ai≤100
 * 
 * 思路：动态规划
 * 1 定义公式 
 *      dp[i][j]: 用前 i 种花摆出 j 盆的方案数量
 * 2 递推关系
 *      dp[i][j] += dp[i][j - k] // 用k个第i种花
 * 3 结果
 *      dp[n][m]
 * 实际dp可以省略第一个维度，但是要注意更改顺序，防止连锁反应
 */

const int N = 105;
using namespace std;
int n, m, dp[N]; // dp[i][j] 用前 i 种花摆出 j 盆

int main() {
    cin >> n >> m;
    if (m < n) {
        cout << 0;
        return 0;
    }

    dp[0] = 1;
    for (int i = 1, a; i <= n; i++) {
        cin >> a;
        for (int j = m; j >= 1; j--) {
            for (int k = 1; k <= min(a, j); k++) // 第 i 种花可以摆几种
                dp[j] += dp[j - k];
            dp[j] %= 1000007;
        }
    }

    cout << dp[m];
    return 0;
}

结果