DP Training M 简单计数DP

DP Training M 简单计数DP

题意

有(N)个孩子分(K)个糖果，第(i)个孩子分到的糖果要在(0)到(a_i)之间

求分配的方案数，模1e9+7

[1 leq N leq 100\ 0 leq K leq 10^5\ 0leq a_i leq K ]

分析

看数据量容易想到(dp[i][j])表示当前枚举到第(i)个人，要掉(j)个糖果的方案数

[dp[i][j] = sum dp[i - 1][j - k] ]

复杂度(O(nk^2))

显然后面是连续的和，可以前缀和优化

空间上，第一维明显可以滚动

代码

ll dp[maxn];
ll a[maxn],sum[maxn];

int main(){
	int n = rd();
	int k = rd();
	for(int i = 0;i < n;i++)
		a[i] = rd();
	dp[0] = 1ll;
	for(int i = 1;i <= n;i++){
		sum[0] = 0;
		for(int j = 1;j <= k + 1;j++) 
			sum[j] = sum[j - 1] + dp[j - 1];
		for(int j = 1;j <= k;j++)
			dp[j] = sum[j + 1] - sum[max(0ll,(ll)j - a[i - 1])],dp[j] %= MOD;
	}
	cout << dp[k];
}