洛谷P1077 [NOIP2012 普及组] 摆花 (DP)

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

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

思路：

m 和 n 的范围都很小，不用对数字类型做特殊处理。至于如何求解，起码你得先搞懂题意，这个题目有一个对应的模板题目：“求和问题”。把题目翻译过来就是有 n 个数字，每个数字有自己的取值范围，从 0 到 ai , 求取出 n 个数字的和刚好为 m 的组合数。m 和 n 的范围都不大，为什么这个题强调了要对结果取模呢？我们先来分析一下这个问题。 对比一下递推公式的推导过程：

摆花时摆当前的花时，需要在摆放完上一盆花产生的结果中进行累加 由于传球游戏只能从左右两个相邻位置相加，所以数字的范围不会太大。但是摆花时，如果当前的花有 10 盆，那么当前的花摆放 0、1、2…10 产生的都是不同的结果，都需要考虑，所以可能的情况是非常多的，可能的情况多，那种对应的方案数也会大，取模就变得很必要了。

根据上述对题目的分析，递推公式也很显然了，假设状态转移都保存在数组 dp[n][m] 中，第一维表示当前对第 i 种花作分析，第二维表示当前摆放的所有的花盆数量和。递推公式如下：

dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + … dp[i-1][j-ai]

dp[i][j] 的含义是放第 i 种花时，花盆总数刚好是 j ，第 i 种花最多有 ai 盆，所以 dp[i-1] 中只要花盆数量大于 j - ai 的情况都能凑成 dp[i][j]。 有了递推公式，问题就解决了一半了，参考代码如下

#include<bits/stdc++.h>
using namespace std;
const int maxn=10005,mod=1e6+7;
int dp[maxn],a[maxn];
int main()
{
    int cnt=0,i,j,n,m;
    cin>>n>>m;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    dp[0]=1;
    for(i=0;i<n;i++)
    {
        for(j=m;j>=0;j--)
        {
            for(int k=1;k<=min(a[i],j);k++)
                dp[j]=(dp[j]+dp[j-k])%mod;
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}