Oiclass P1238 题解

又是一道烧脑的模板题

进入正题，以下是传统得无与伦比的五步

1. 划分阶段

这里以每一种花为一个阶段，表示从第 \(1\) 种花到这一种花之间的所有花一共最多能有几种方案

2. 状态和状态变量

直接用一个二维数组 \(f\) 用来存状态，状态： \(f_{i,\ j}\) 表示 表示第 \(i\) 种花共摆了 \(j\) 盆时一共最多能有几种方案，也就是一个最优解。

3. 确定决策和状态转移方程

这里，状态还算简单： \[ f_{i,\ j}=f_{i,\ j} + f_{i-1,\ j-k} \] 不过如果你直接这样算，会直接爆掉，因为你忘记 \(\%1000007\) 这是非常重要的一个部分，所以改进一下，方程应改变成这样： \[ f_{i,\ j}=(f_{i,\ j}+f_{i-1,\ j-k}) \]

4. 边界

\[ f_{0\to n,\ 0}=1 \]

5. 实现：

#include <iostream>
#include <cstring>

using namespace std;

int m, n, a[109], f[109][109];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i][0] = 1;
        for (int j = 1; j <= m; j++) {
            for (int k = 0; k <= min(j, a[i]); k++) {
                f[i][j] = f[i - 1][j - k] + f[i][j];
                f[i][j] %= 1000007;
            }
        }
    }
    cout << f[n][m] % 1000007;
}