本题做法
- DP。
思路
定义 \(dp[i][j]\) 表示前 \(i\) 种花摆好之后一共摆了 \(j\) 盆花的方案数。则有状态转移方程：
\[dp[i][j]=\sum_{k=0}^{\min(j,a[i])}{dp[i-1][j-k]}
\]
直接按照上面的算，最终输出 \(dp[n][m]\) 就行了。
代码
#include<bits/stdc++.h>using namespace std;typedef long long ll;
typedef unsigned long long ull;const int N=105;
const int MOD=1e6+7;int n,m,a[N],dp[N][N];
// dp[i][j]：第i种花摆完了，一共摆了j盆花 int main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n>>m;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<=min(j,a[i]);k++){dp[i][j]+=dp[i-1][j-k];dp[i][j]%=MOD;}}}cout<<dp[n][m]<<endl;return 0;
}