Luogu-P1077-摆花

Posted on Edited on Word count in article: 667

题目 P1077 [NOIP2012 普及组] 摆花

题目描述

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

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

输入格式

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

第二行有 nn 个整数，每两个整数之间用一个空格隔开，依次表示 a1,a2,⋯ ,ana_1,a_2, \cdots ,a_n。

输出格式

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

思路：dp

dp表

dp[i][j]dp[i][j]：前 ii 种花放 jj 盆的方案数

状态

  • 初状态：

    00 个物品放 00 个的方案数为 11，因此以下状态恒成立。

    1
    dp[0][0] = 1;

    另外，根据循环方式不同，有不同的初状态。详见补充部分。

  • 状态转移方程：

    在前 ii 种花一共有 jj 盆的情况下，如果不考虑最大盆数的限制，那么第 ii 种花的盆数x∈[0,j]x \in [0,j]。得到前 (i−1)(i-1) 种花的盆数就是 j−xj-x。

    所以第 ii 种花的方案数是前 i−1i-1 种花的方案数之和。

    因此对于前 ii 种花，存在如下的关系。

    dp[i][j]=dp[i−1][0]+dp[i−1][1]+⋯+dp[i−1][j]dp[i][j] = dp[i-1][0]+dp[i-1][1]+ \cdots +dp[i-1][j]

    但是，本题限制了最大盆数 aia_i。因此，x∈[0,min⁡(ai,j)]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]dp[n][m]。

AC Code

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
// template v7
#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;
}

补充

另外的循环方式

对应状态

  • 初状态

    因为不管是前几个物品，摆放 00 盆的方案数总为 11。所以不妨考虑所有的 i∈1∼ni \in 1 \sim n，以下状态恒成立。

    1
    dp[i][0] = 1;

    此时，jj 的遍历就不应是 0∼m0 \sim m 了。因为 dp[i][0]dp[i][0] 恒为 11，而当 j=k=0j=k=0 时，会在 dp[i][j]+=dp[i−1][j−k]dp[i][j]+=dp[i-1][j-k] 处产生 dp[i][0]+=dp[i−1][0]dp[i][0]+=dp[i-1][0]，不合理。

    所以此时 j∈1∼mj \in 1 \sim m。

  • 状态转移方程和末状态同上。

AC Code

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
// template v7
#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][j] += dp[i - 1][j - k] 中，dp[i][⋯ ]dp[i][ \cdots ] 只与 dp[i−1][⋯ ]dp[i-1][\cdots] 有关。

因此，考虑滚动数组。

同时，为了保证在第 ii 盆花时，只改变一次数组的值，应该使用倒序循环。

AC Code

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
// template v7
#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;
}