洛谷P1077题（2012年NOIP普及组）：用动态规划解决摆花问题

一、题目解读

洛谷P1077摆花问题考察动态规划的实际应用。题目要求用n种花摆出m盆花束，每种花有数量限制a[i]，需要计算所有可能的摆放方案数。这个问题在算法竞赛中具有典型性，能帮助学习者掌握多重背包问题的变种解法。

二、解题思路

1. 问题转化：将每种花看作背包问题中的物品，花盆数量对应背包容量

2. 状态定义：DP[i][j]表示前i种花摆放j盆的方案数

3. 转移方程：通过三重循环实现状态转移，考虑每种花摆放0到a[i]盆的所有可能

4. 模数处理：使用1e6+7作为模数避免整数溢出

三、解题步骤

1. 初始化二维dp数组，边界条件dp[i][0]=1

2. 外层循环遍历花种类（1-n）

3. 中层循环遍历目标花盆数（1-m）

4. 内层循环枚举当前种类花的摆放数量（0-min(a[i],j)）

5. 状态转移：dp[i][j] += dp[i-1][j-k]

6. 最终输出dp[n][m]%MOD的结果

四、完整代码

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e6 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1); // 花的数量限制，从1开始编号
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    
    // dp[i][j]表示前i种花摆放j盆的方案数
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    
    // 初始化：前i种花摆放0盆的方案数为1（什么都不放）
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = 1;
    }
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            // 第i种花可以放0到min(a[i],j)盆
            for (int k = 0; k <= a[i] && k <= j; ++k) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
            }
        }
    }
    
    cout << dp[n][m] << endl;
    return 0;
}

五、总结

本题展示了动态规划解决组合计数问题的典型模式。关键点在于：

1. 准确识别子问题重叠特性

2. 合理设计状态表示

3. 正确处理模运算 建议学习者尝试空间优化（降维）和思考其他边界情况的处理方式。