♐ CSP_J 组真题
2012年
3. 摆花

线上OJ:

一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1959 (opens in a new tab)
AcWing:https://www.acwing.com/problem/content/description/453/ (opens in a new tab)
洛谷:https://www.luogu.com.cn/problem/P1077 (opens in a new tab)

核心思想:

1、这是一道 动态规划DP 的题目,问的是**给定n种花,摆出m盆的方案总数**。
2、由于原文中提到“摆花时 同一种花放在一起,且 不同种类的花按标号 的从小到大的 顺序 依次 摆列” 也就是类似 “1112233344” 这种排法,故本题中不涉及到排列组合问题。我们设 f[i][j]f[i][j] 为给 i 种花, 摆放 j 盆时的方案总数,则最终要求结果就是 f[n][m]。
3、很明显,f[i][j] 是从 i-1 种花的方案推导过来的。如果 i 种花的数量是 k 盆0km,ka[i](0 ≤ k ≤ m, k ≤ a[i]),则 i-1 种花摆放的数量就是 j-k 盆。所以

💡

f[i][j]=0kmka[i](f[i1][jk]);f[i][j] = \sum\limits_{\substack{0 \leq k \leq m \\ k \leq a[i]}}(f[i-1][j-k]);

4、注意初始化 f[i][0]=1f[i][0] = 1。 表示前 i 种花,摆放0盆的方案数是1,就是都不摆。初始化时要从f[0][0]开始,否则f[1][1]数据会出错

题解代码:

解法一、动态规划
解法一、动态规划:
#include <bits/stdc++.h>
#define MOD 1000007
using namespace std;
 
const int N = 105;
int n, m;
int a[N], f[N][N]={0};  // a[i]表示第i种花最多多少盆; f[x][y]记录前i种花,摆放了共j盆的方案数
 
/* 核心思想:动态规划,f[i][j] 从前面的 f[i-1][j-k] 传递过来。
故设 f[i][j] 表示前i种花,摆放了共j盆的方案数
*/
int main()
{
    scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++)  scanf("%d", &a[i]);
 
	for(int i = 0; i <= n; i++)  f[i][0] = 1;  // 前i种花,摆放0盆的方案数是1,就是都不摆。初始化时要从f[0][0]开始,否则f[1][1]数据会出错
 
	for(int i = 1; i <= n; i++)   // 前i种花
        for(int j = 1; j <= m; j++) // 共拜访了j盆, j<=m
            for(int k = 0; k <= min(a[i], j); k++)  // 第i种花摆放了k盆,k<=m,k<=a[i],则前i-1种花摆放了j-k盆
                f[i][j] = (f[i][j] + f[i-1][j-k]) % MOD;    // 方程
 
	cout << f[n][m]; // 从第 1 种花要摆放 m 盆开始深搜
	return 0;
}