摆花
思路
\(\text { 有 } n \text { 个数 }\left(c_{1}, c_{2}, \ldots, c_{n}\right) ， 0 \leqslant c_{i} \leqslant a_{i} \text {, 求有多少种方案数使 } \sum_{i=1}^{n} c_{i}=m \text { 。 }\)
\(f(i，j)表示前i个数总和为j的方案数\)
\(状态转移方程f(i，j) = \sum_{k=0}^{a_i}f(i-1,j-k)\)
代码
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
typedef long long LL;
const char nl = '\n';
const int N = 110;
const int M = 1e6+10;
const int mod = 1e6+7;
int n,m,q;
int a[N],f[N][N];
//记忆化搜索
// int dfs(int x,int k){ //x种物品体积为k的方案数
// if(f[x][k])return f[x][k];
// if(k > m)return 0;
// if(k == m)return 1;
// if(x == n + 1)return 0;
// int ans = 0;
// for(int i = 0; i <= a[x]; i ++)ans = (ans + dfs(x+1,k+i))%mod;
// return f[x][k] = ans;;
// }
void solve(){
cin >> n >> m;
for(int i = 1; i <= n; i ++ )cin >> a[i];
f[0][0] = 1;
for(int i = 1; i <= n; i ++){ //枚举前i种物品
for(int j = 0; j <= m; j ++){ //枚举总和
for(int k = 0; k <= min(j,a[i]); k ++){ //枚举每种物品选多少个(不能超过a[i]也不能超过总和)
f[i][j] = (f[i][j] + f[i-1][j-k])%mod;
}
}
}
cout << f[n][m] << nl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
}