算法：DP
看到这题真的一点不会。。。只能爆搜一下。。但太太慢了。。看了题解后，听说是分组背包？？不知道。。
好吧，，还是百度了下题解，渐渐明了。。
我们用f(i, j)来表示前i种花摆j盆的最大方案数，可以推得
f(i, j) = sum{ f(i-1, j-k) | 0<=k<=a[i], 其中a[i]为i种花的盆数 }
在这里，我们可以简化为一维的~
f(j) = sum{ f(j-k) | 0<=k<=a[i], 其中a[i]为i种花的盆数 }
这是为什么呢？我们可以这样想，第i种花要么摆1朵，要么摆2朵...要么摆a[i]朵，要么不摆。那么方案数就为它所有能摆的方案数之和
好了，上代码~一维的。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 |
#include <cstdio>using
namespace std;#define FOR(i, a, n) for(i = a; i <= n; ++i)const
int MAX = 110, MOD = 1000007;int i, j, k, n, m, a[MAX], f[MAX];int main() { scanf("%d%d", &n, &m); FOR(i, 1, n) scanf("%d", &a[i]); f[0] = 1; FOR(i, 1, n) for(j = m; j >= 0; --j) FOR(k, 1, a[i]) if(j-k >= 0) f[j] = (f[j] + f[j-k]) % MOD; printf("%d", f[m]); return
0;} |
原文：http://www.cnblogs.com/iwtwiioi/p/3550810.html