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

一、题目解读

洛谷P1077题目要求计算在给定n种花和m盆的情况下，满足每种花数量不超过其限制条件时，总共有多少种不同的摆放方案。题目本质是一个经典的组合数学问题，需通过合理的算法设计来高效求解。

二、解题思路

观察到题目中每种花的数量存在上限，且总盆数固定，此类问题常与动态规划中的“背包问题”思路关联。关键在于设计状态转移方程：用dp[i][j]表示前i种花摆放j盆的方案数。通过枚举第i种花的摆放数量，结合前i-1种花的方案，推导出当前状态的可能组合。

三、解题步骤

1. 初始化：定义dp数组，前i种花不摆放（j=0）的方案数为1（即空集）。

2. 状态转移：外层循环遍历花种类i，内层循环遍历总盆数j，并枚举第i种花的摆放数量k（0~min(a[i],j)）。

3. 核心逻辑：dp[i][j] += dp[i-1][j-k]，即当前方案数等于不选第i种花（dp[i-1][j]）与选择k盆第i种花（dp[i-1][j-k]）的方案数之和，取模避免溢出。

4. 结果输出：最终dp[n][m]即为所求方案总数。

四、代码与注释

#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;  
}

注释说明：通过动态规划递推，利用状态转移方程优化计算，避免重复组合，确保结果正确且高效。

五、总结

洛谷P1077通过动态规划将组合问题转化为状态转移的求解，核心在于理解“前缀和”与“局部选择”的关系。合理设计dp数组和边界条件，能有效降低时间复杂度。在实际应用中，此类思路可扩展至多约束条件的组合优化场景。