题目描述
小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 $m$ 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 $n$ 种花，从 $1$ 到 $n$ 标号。为了在门口展出更多种花，规定第 $i$ 种花不能超过 $a_i$ 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算，一共有多少种不同的摆花方案。
输入格式
第一行包含两个正整数 $n$ 和 $m$，中间用一个空格隔开。
第二行有 $n$ 个整数，每两个整数之间用一个空格隔开，依次表示 $a_1,a_2, \cdots ,a_n$。
输出格式
一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 $10^6+7$ 取模的结果。
思路：dp
dp表
$dp[i][j]$：前 $i$ 种花放 $j$ 盆的方案数
状态
初状态：
$0$ 个物品放 $0$ 个的方案数为 $1$，因此以下状态恒成立。
另外，根据循环方式不同，有不同的初状态。详见补充部分。
状态转移方程：
在前 $i$ 种花一共有 $j$ 盆的情况下，如果不考虑最大盆数的限制，那么第 $i$ 种花的盆数$x \in [0,j]$。得到前 $(i-1)$ 种花的盆数就是 $j-x$。
所以第 $i$ 种花的方案数是前 $i-1$ 种花的方案数之和。
因此对于前 $i$ 种花，存在如下的关系。
$dp[i][j] = dp[i-1][0]+dp[i-1][1]+ \cdots +dp[i-1][j]$
但是，本题限制了最大盆数 $a_i$。因此，$x \in [0,\min(a_i,j)]$。
所以状态转移方程为：
1
| dp[i][j] = dp[i - 1][0] + dp[i - 1][1] + ... + dp[i - 1][min(a[i],j)];
|
末状态：$dp[n][m]$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline void minset(int &t, int other) {
t = min(t, other);
}
inline void maxset(int &t, int other) {
t = max(t, other);
}
const int inf = 0x7f7f7f7f;
const int N = 110;
const int M = 110;
const int MOD = 1e6 + 7;
int lim[N];
int dp[N][M];
int main() {
int n, m;
cin >> n >> m;
dp[0][0] = 1;
for(int i = 1; i <= n; i++) {
cin >> lim[i];
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= m; j++) {
for(int k = 0; k <= min(j, lim[i]); k++) {
dp[i][j] += dp[i - 1][j - k];
dp[i][j] %= MOD;
}
}
}
cout << dp[n][m] << endl;
return 0;
}
|
补充
另外的循环方式
对应状态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline void minset(int &t, int other) {
t = min(t, other);
}
inline void maxset(int &t, int other) {
t = max(t, other);
}
const int inf = 0x7f7f7f7f;
const int N = 110;
const int M = 110;
const int MOD = 1e6 + 7;
int lim[N];
int dp[N][M];
int main() {
int n, m;
cin >> n >> m;
dp[0][0] = 1;
for(int i = 1; i <= n; i++) {
cin >> lim[i];
dp[i][0] = 1;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
for(int k = 0; k <= min(j, lim[i]); k++) {
dp[i][j] += dp[i - 1][j - k];
dp[i][j] %= MOD;
}
}
}
cout << dp[n][m] << endl;
return 0;
}
|
优化
原因
注意到，状态转移方程 $dp[i][j] += dp[i - 1][j - k]$ 中，$dp[i][ \cdots ]$ 只与 $dp[i-1][\cdots]$ 有关。
因此，考虑滚动数组。
同时，为了保证在第 $i$ 盆花时，只改变一次数组的值，应该使用倒序循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline void minset(int &t, int other) {
t = min(t, other);
}
inline void maxset(int &t, int other) {
t = max(t, other);
}
const int inf = 0x7f7f7f7f;
const int N = 110;
const int M = 110;
const int MOD = 1e6 + 7;
int lim[N];
int dp[M];
int main() {
int n, m;
cin >> n >> m;
dp[0] = 1;
for(int i = 1; i <= n; i++) {
cin >> lim[i];
}
for(int i = 1; i <= n; i++) {
for(int j = m; j >= 0; j--) {
for(int k = 1; k <= min(j, lim[i]); k++) {
dp[j] += dp[j - k];
dp[j] %= MOD;
}
}
}
cout << dp[m] << endl;
return 0;
}
|