总共要摆m盆花，而每种花最多有a[i]盆。仔细思索，发现它是一个多重背包求方案数问题。但是我蒟蒻的不会，于是跑去问大佬。
以下状态转移方程及化简from rqy
如果第i个物品有a[i]，每个的体积是b[i],设f[i][j]为前i个物品占用体积为j的空间的方案数
则：f[i][j]=f[i-1][j]+f[i-1][j-b[i]]+f[i-1][j-2*b[i]]+………………+f[i-1][j-a[i]*b[i]] （f[i][j]可以由f[i-1][j]什么都不选得来，可以由f[i-1][j-b[i]]再选一个第i种物品得来……）
运用到这个题里，显然每盆花的体积是1，状态转移方程就是：
f[i][j]=f[i-1][j]+f[i-1][j-1]+f[i-1][j-2]+..........+f[i-1][j-a[i]]
看到这里，我们就可以写出三层循环的代码了
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int n,m,a[105]; long long f[105][105]; const int mod=1000007; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); f[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++) { f[i][j]+=f[i-1][j-k]; f[i][j]=(f[i][j]+mod)%mod; } } } printf("%d",(f[n][m]+mod)%mod); }
这样就可以ac了
但是这个方程很长有木有，看起来好像可以化简有木有
对比f[i][j-[b[i]]=f[i-1][j-b[i]]+f[i-1][j-2*b[i]]+......+f[i-1][j-b[i]-(a[i]-1)*b[i]]+f[i-1][j-b[i]-a[i]*b[i]]
发现f[i][j]=f[i-1][j]+f[i][j-b[i]]-f[i-1][j-(a[i]+1)*b[i]]
amazing!
那这个化简后的方程怎么理解呢？
这就相当于说f[i][j]要么从f[i-1][j]一盆第i种花也不选，直接推过来，要么第i种已经选了1盆了，再来一盆第i种（f[i][j-b[i]]）,但是如果你第i种已经选了ai盆了，就不能再继续选了，所以要把选了ai盆后再选的方案数减掉（因为选ai盆是合法的，而选ai+1盆才是不合法的，所以是减f[i-1][j-(a[i]+1)*b[i]]）
但是蒟蒻懒得不会打代码qwq