[luoguP1077] 摆花(DP)

传送门

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

             j

f[i][j] =  Σ  f[i - 1][j]

       k=max(0, j - a[i])

博客园这个公式该怎么打啊。。

——代码(本渣太菜,和公式有些不同)

 1 #include <cstdio>
 2 
 3 int n, m, p = 1000007;
 4 int a[201], f[201][201];
 5 
 6 int main()
 7 {
 8     int i, j, k;
 9     scanf("%d %d", &n, &m);
10     for(i = 1; i <= n; i++) scanf("%d", &a[i]);
11     for(i = 0; i <= a[1]; i++) f[1][i] = 1;
12     for(i = 1; i < n; i++)
13         for(j = 0; j <= m; j++)
14             for(k = 0; k <= a[i + 1]; k++)
15                 if(f[i][j])
16                     f[i + 1][j + k] = (f[i + 1][j + k] + f[i][j]) % p;
17     printf("%d
", f[n][m]);
18     return 0;
19 }
View Code
原文地址:https://www.cnblogs.com/zhenghaotian/p/6838240.html