侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【线性DP】摆花

GabrielxD
2023-04-25 / 0 评论 / 0 点赞 / 221 阅读 / 1,032 字
温馨提示:
本文最后更新于 2023-04-25,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

试题 算法提高 摆花

451. 摆花 - AcWing题库


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

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

输入

第一行包含两个正整数 nnmm ,中间用一个空格隔开。

第二行有 nn 个整数,每两个整数之间用一个空格隔开,依次表示 a1,a2,na_1, a_2, \dots n

输出

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

样例输入

2 4
3 2

样例输出

2

输入输出样例说明

22 种摆花的方案,分别是 (1,1,1,2),(1,1,2,2)(1, 1, 1, 2), \enspace (1, 1, 2, 2) 。括号里的 1122 表示两种花,比如第一个方案是前三个位置摆第一种花,第四个位置摆第二种花。

数据规模和约定

  • 对于 20%20\%数据,有 0<n8,0<m8,0ai80<n≤8, 0<m≤8, 0≤a_i≤8
  • 对于 50%50\%数据,有 0<n20,0<m20,0ai200<n≤20, 0<m≤20, 0≤a_i≤20
  • 对于 100%100\% 数据,有 0<n100,0<m100,0ai1000<n≤100, 0<m≤100, 0≤a_i≤100

解题

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

思路

把花盆数量看作背包容量, nn 种花看作 nn 种体积为 11 价值为 11 的物品,第 ii 种物品最多可以选择 aia_i 个,问题则变为:将背包装满的方案数共有多少个。此时这题就变为了经典的多重背包求方案数问题。

动态规划:

  • 状态定义: f[i][j]f[i][j] 表示所有只考虑前 ii 个朵花,装满前 jj 个花盆的所有方案数;
  • 状态转移方程: f[i][j]=k=0a[i]f[i1][jk]f[i][j] = \sum_{k=0}^{a[i]}{f[i - 1][j - k]}
  • 初始状态: f[0][0]=1f[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]);
    }
}
0
博主关闭了所有页面的评论