Luogu P1077 摆花 题解

题目链接：Luogu P1077 摆花

---

题目大意

一共 \(n\) 个位置，每个位置可以放不超过 \(a[i]\) 盆花，问一共放了 \(m\) 盆的方案数。

题解

设 \(\text{dp}[i][j]\) 表示只考虑前 \(i\) 个位置，且和为 \(j\) 的方案数，则有：

\[\text{dp}[i][j] = \sum_{k=0}^{\text{min}(j, a[i])}{\text{dp}[i-1][j-k]}\]

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 100 + 5;
const int MOD = 1000007;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
    for (c = getchar(); !isdigit(c); c = getchar());
    for(a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

int a[N], n, m;
ll \text{dp}[N][N];

int main() {
    //freopen("t5.in", "r", stdin);
    read(n), read(m);
    for(int i = 1; i <= n; i++) {
        read(a[i]);
    }
    \text{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++) {
                if(j - k >= 0) {
                    \text{dp}[i][j] = (\text{dp}[i][j] + \text{dp}[i - 1][j - k]) % MOD;
                }
            }
        }
    }
    cout << \text{dp}[n][m] << endl;
    return 0;
}