嗯...

 

题目链接：https://www.luogu.org/problemnew/show/P1077

 

这是一道典型的DP问题：

　　我们用dp[i][j]表示放第i种花，放j盆的放法。

　　首先进行初始化，无论有多少种花，如果一盆都没有，只有一种方案总数。

　　k是用于计算某种花放多少盆，从总盆数开始循环到（总盆数-最大盆数），如果k小于0（说明最大盆数大于总盆数）就退出循环，

　　我们把dp数组的行也就是dp[i][]看成是每一种花的位置，所以我们得到状态转移方程：

b[i][j]=b[i][j]+b[i-1][k]

　　这个方程的意思是：我当前这个第i种花放的方法数+上一种花放k盆的方法数叠加

 

AC代码：

1 #include
      
        2 #include
       
         3  4 using namespace std; 5  6 const int maxn = 10005; 7 const int mod = 1000007; 8  9 int n, m;10 long long a[maxn], dp[maxn][maxn];11 12 int main(){13     scanf("%d%d", &n, &m);14     for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);15     for(int i = 0; i <= m; i++) dp[i][0] = 1;16     for(int i = 1; i <= n; i++){17         for(int j = 1; j <= m; j++){18             for(int k = j; k >= j - a[i]; k--){19                 if(k >= 0){20                     dp[i][j] += dp[i - 1][k] % mod;21                     dp[i][j] %= mod;22                 }23                 else break;24             }25         }26     }27     printf("%lld\n", dp[n][m]);28     return 0;29 }