P1077 [NOIP 2012 普及组] 摆花

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

const int MOD = 1000007;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    // f[i][j]：只用前 i 种花摆出 j 盆的方案数
    vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
    f[0][0] = 1; // 什么都不摆，恰好 0 盆，有 1 种方案

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            // 第 i 种花摆 k 盆，剩下 j-k 盆交给前 i-1 种花
            for (int k = 0; k <= a[i] && k <= j; k++) {
                f[i][j] = (f[i][j] + f[i - 1][j - k]) % MOD;
            }
        }
    }

    cout << f[n][m] << "\n";
    return 0;
}