摆花动态规划

前言：其实我在想这个问题的时候也考虑了，这不是妥妥的符合动态规划的特点吗， i 时刻的状态只和 i - 1 的状态有关，但是写着写着就不对劲了
后来发现是下标写错了
我们用 dp[ i ] 表示选取 i 个花盆的个数
对于每一个 a[ i ] 我们都要枚举选一个还是 a[ i ] 个，注意 a[ i ] 与 m的大小关系，每次 ans 都加上每种情况的答案
接着我们需要更新 dp
我们可以选择只要第 i 种花，也可以搭配i之前的花，
我们设置 dp[0] = 1
然后可以合并这两种情况，从 m 开始到 0 倒序，只有 dp[ i ] 的值不为 0 才进行更新

---

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;#define int long long
int n,m;
const int N = (300);
int a[N];
int dp[N];
const int Mod = (int)1e6+7;signed main(){cin >> n >> m;int ans = 0;for(int i=1;i<=n;i++) cin >> a[i];dp[0] = 1;for(int i=1;i<=n;i++){int t = a[i];for(int j=min(m,t);j>=1;j--){ans += dp[(m-j)];}//if(t>=m) ans++;ans %= Mod;// 还有前缀的 for(int j=m;j>=0;j--){for(int k=1;k<=t;k++){if(j+k>m) break;if(dp[j]==0) continue;dp[j+k] = (dp[j] + dp[j+k]) % Mod;}}
//		for(int j=1;j<=t;j++){
//			dp[j] =(dp[j] + 1) % Mod;
//		}}cout << ans;return 0;
}