P1077 摆花

题目描述

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

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

输入格式

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

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

有 $0 < n \leq 100, 0 < m \leq 100, 0 \leq a_{i} \leq 100$ 。

输出格式

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

Solution

DP/记忆化搜索

题解 P1077 【摆花】 - 洛谷专栏

普通DP

const int mod = 1e6 + 7;
int dp[110][110];//前i个数和为j的方案数
void solve() {
    int n, m;cin >> n >> m;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    dp[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++) {
                dp[i][j] += dp[i - 1][j - k];dp[i][j] %= mod;
            }
        }
    }
    cout << dp[n][m];
}

滚动数组优化的 DP

int dp[2][110];
void solve() {
    int n, m;cin >> n >> m;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    int t = 0;
    dp[0][0] = 1;
    for (int i = 1;i <= n;i++) {
        t ^= 1;
        for (int j = 0;j <= m;j++) {
            dp[t][j] = 0;
            for (int k = 0;k <= a[i] && k <= j;k++) {
                dp[t][j] += dp[t ^ 1][j - k];dp[t][j] %= mod;
            }
        }
    }
    cout << dp[t][m];
}

01背包 DP

void solve() {
    int n, m;cin >> n >> m;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    vector<int> dp(m + 1);dp[0] = 1;
    for (int i = 1;i <= n;i++) {
        for (int j = m;j >= 0;j--) {
            for (int k = 1;k <= a[i] && k <= j;k++) {
                dp[j] += dp[j - k];dp[j] %= mod;
            }
        }
    }
    cout << dp[m];
}

前缀和优化 $O (m n)$ (没懂)

void solve() {
    int n, m;cin >> n >> m;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    vector<int> dp(m + 1), sum(m + 1);
    dp[0] = 1;
    for (int i = 0;i <= m;i++)sum[i] = 1;
    for (int i = 1;i <= n;i++) {
        for (int j = m;j >= 1;j--) {
            int t = j - min(a[i], j) - 1;
            if (t < 0)dp[j] = (dp[j] + sum[j - 1]) % mod;
            else dp[j] = (dp[j] + sum[j - 1] - sum[t] + mod) % mod;
        }
        for (int j = 1;j <= m;j++) {
            sum[j] = (sum[j - 1] + dp[j]) % mod;
        }
    }
    cout << dp[m];
}

生成函数 $(m a r k)$