[每日算法]摆花

题目描述

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

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

输入格式

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

第二行有n 个整数，每两个整数之间用一个空格隔开，依次表示a₁,a₂,⋯,a_n。

输出格式

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

输入输出样例

样例#1	输出#1
2 4 3 2	2

说明/提示

• 【数据范围】

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

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

  对于100% 数据，有 0<n≤100,0<m≤100,0≤a_i≤100。

题解

这是个典型的动态规划问题，即可以从之前的状态推出后面的状态的最优解。用数组arr表示每种花最多的盆数，用二维数组fx存储i种j盆花的方案数。那么可以从初始状态fx【i】【0】=1（即一盆花都没有时，只有一种方案）出发。状态转移方程为 fx【i】【j】 += fx【i - 1】【k】。核心其实是从上一层的最优解推下一层的最优解，这个题的最优即所有方案加起来的和，所以这个题不需要取max,min。

源代码

#include <iostream>
using namespace std;

int arr[101], fx[101][101];//arr为每种花最多的盆数，fx存储放i种j盆花的方案数
int main()
{
    int i, j, k;
    int mod = 1000007;
    int n, m;
    cin >> n >> m;      //获取花的总数和盆数
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
    for (int i = 0;i <= m;i++)
    {//进行初始化，一盆花都没有时，就只有一种方案
        fx[i][0] = 1;
    }
    for (i = 1;i <= n;i++)
    {//花的种类
        for (j = 1;j <= m;j++)
        {//这种花的盆数
            for (k = j;k >= j - arr[i];k--)
            {//k为这种花的盆数,状态转移方程
                if (k < 0) break;   //及时终止循环
                fx[i][j] += fx[i - 1][k] % mod;
                fx[i][j] %= mod;
            }
        }
    }
    cout << fx[n][m] << endl;       //输出总数
    return 0;
}