【线性DP】摆花

题目

试题 算法提高 摆花

451. 摆花 - AcWing题库

---

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

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

输入

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

第二行有 $n$ 个整数，每两个整数之间用一个空格隔开，依次表示 $a_1, a_2, \dots n$ 。

输出

输出只有一行，一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 $1000007$ 取模的结果。

样例输入

2 4
3 2

样例输出

2

输入输出样例说明

有 $2$ 种摆花的方案，分别是 $(1, 1, 1, 2), \enspace (1, 1, 2, 2)$ 。括号里的 $1$ 和 $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$ 。

解题

方法一：线性DP - 多重背包模型 - 背包问题求方案数

思路

把花盆数量看作背包容量， $n$ 种花看作 $n$ 种体积为 $1$ 价值为 $1$ 的物品，第 $i$ 种物品最多可以选择 $a_i$ 个，问题则变为：将背包装满的方案数共有多少个。此时这题就变为了经典的多重背包求方案数问题。

动态规划：

• 状态定义： $f[i][j]$ 表示所有只考虑前 $i$ 个朵花，装满前 $j$ 个花盆的所有方案数；
• 状态转移方程： $f[i][j] = \sum_{k=0}^{a[i]}{f[i - 1][j - k]}$ ；
• 初始状态： $f[0][0] = 1$ ；

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int MOD = 1000007;
    static int n, m;
    static int[] a;

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); n = (int) in.nval;
        in.nextToken(); m = (int) in.nval;
        a = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            in.nextToken(); a[i] = (int) in.nval;
        }
        int[][] f = new int[n + 1][m + 1];
        f[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) {
                    f[i][j] = (f[i][j] + f[i - 1][j - k]) % MOD;
                }
            }
        }
        System.out.println(f[n][m]);
    }
}

优化为一维数组：

import java.util.*;
import java.io.*;

public class Main {
    static final int MOD = 1000007;
    static int n, m;

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); n = (int) in.nval;
        in.nextToken(); m = (int) in.nval;
        int[] f = new int[m + 1];
        f[0] = 1;
        for (int i = 0; i < n; ++i) {
            in.nextToken(); int a = (int) in.nval;
            for (int j = m; j >= 0; --j) {
                for (int k = 1; k <= a && k <= j; ++k) {
                    f[j] = (f[j] + f[j - k]) % MOD;
                }
            }
        }
        System.out.println(f[m]);
    }
}