普及组2012 洛谷 1077 摆花

题目：摆花

思路：

DP。

f[i][j]表示前i种花摆j盆的方案数。

转移方程：f[i][j]=f[i-1][j]+f[i-1][j-k] ，k为第i种花摆的盆数。

可以用滚动数组优化空间去掉第一维。

代码：

#include<bits/stdc++.h>
using namespace std;#define md 1000007
#define maxn 100 int n,m;
int a[maxn+5];
int f[maxn+5]={0};  int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);f[0]=1;for(int i=1;i<=n;i++){for(int j=m;j>=1;j--){for(int k=1;k<=a[i];k++){if(k<=j) f[j]=(f[j]+f[j-k])%md;else break;}}}printf("%d",f[m]);return 0;
}