摆花问题题解

题意

题目描述

小明要在花店门口摆放$m$盆花，共有$n$种花。

每种花最多摆放$a_{i}$盆，且同种花必须放在一起，不同种类花要按照编号顺序摆放。

要求计算所有可能的摆放方案数，结果对$10^6+7$取模。

测试用例分析

输入样例1：‌

2 4
3 2

输出样例1：‌

2

分析：‌

有$2$种花 共摆放$4$盆

第$1$种花最多$3$盆$(a_{1}=3)$ 第$2$种花最多$2$盆$(a_{2}=2)$

可能的方案：

$$第一种花2盆,第二种花2盆$$ $$第一种花3盆,第二种花1盆$$

其他组合要么超过限制，要么总数不足$4$盆

---

解题思路

1.40wa的做法

记录

可以使用递归枚举所有可能的摆放组合：

对于每种花，尝试摆放$0$到$a_{i}$盆

确保总盆数不超过==$m$==

当所有花都考虑完后，如果总盆数正好是$m$，则方案数$+1$

代码

#include <iostream>
using namespace std;
const int modder = 1e6 + 7;
int n, m;
int a[105];
int cnt = 0;
void dfs(int cst, int ree) {
    if (cst==n) {
        if (ree == 0) {
            cnt=(cnt+1)%modder;
        }
        return;
    }
    for (int i=0;i<=a[cst]&&i<=ree;i++) {
        dfs(cst+1,ree-i);
    }
}
int main() {
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    dfs(0,m);
    cout<<cnt<<endl;
    return 0;
}

这种方法时间复杂度为高，当$n$和$a_{i}$较大时会超时。

---

动态规划解法(100ac的解法)

使用动态规划来优化：

定义$dp[i][j]$表示前i种花摆放j盆的方案数

状态转移方程：

$$dp[i][j] = dp[i][j]+dp[i-1][j-k] (0 ≤ k ≤ min(a[i], j)) $$

初始条件：$dp[0][0] = 1$ 最终答案：$dp[n][m]$

这种方法时间复杂度为$O(nm*max_a)$，空间复杂度$O(nm)$

代码实现

#include<bits/stdc++.h>
using namespace std;
const int modd = 1e6 + 7;
int dp[105][105]; // dp[i][j]表示前i种花摆放j盆的方案数
int a[105]; // 每种花的最大数量限制

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 <= a[i] && k <= j; k++) { // 当前花摆放k盆
                dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % modd;
            }
        }
    }
    
    cout << dp[n][m] << endl;
    return 0;
}