lanqiao OJ 389 摆花

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std ;
typedef long long LL ;//不开longlong见祖宗
const LL N = 110 , M = 1000007 ;
LL f[N][N] ;// 状态表示  前i种花摆放j个位置的方案数量
LL a[N] ;
int main(){
  int n , m ; cin >> n >> m ;
  for(int i = 1 ; i <= n ;i ++){
    cin >> 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 <= a[i]&& k <= m && j - k >= 0 ; k ++){
                //进行三个特判 1.不能超过最多能添加的数量
                                //2.不能超过所给位置的数量
                                  //3.给j的范围特判以下 不要越界
        f[i][j] = (f[i][j] + f[i-1][j-k]) % M ;
      }
    }
  }
  cout << f[n][m] << endl ;
  return 0 ;
}