DPまとめコンテスト M - Candies

M - Candies

概要

項の数列と、整数が与えられる。下記の条件を満たす数列の個数を求めよ。
（出力はmod ）

• 
• 

（個の飴を人の子供に配る）

制約

方針

dp[i][j] : i-1番目の子供で飴がj個余るときの分け合う方法数　とし、DPする。
基本的な遷移式は下記の通り。
dp[i+1][j] = dp[i][j] + dp[i][j+1] + dp[i][j+2] + ... + dp[i][j+a[i]]

ただし、計算量・メモリともに制約があるので下記の工夫を行う。

工夫①：
dp[i+1][j]はdp[i+1][j+1]を用いると下記のように表せる。
dp[i+1][j] = dp[i+1][j+1] + dp[i][j] - dp[i][j+1+a[i]]
すなわち、毎回j, j+1, ... , j+a[i]を計算するのでなく、頭とおしりのみを更新してゆくイメージ。

工夫②：
保持するのは前回の結果だけでよいので、インデックスiはmod 2でOK

解答

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n, k;
	cin >> n >> k;
 
	ll a[n];
	rep(i, n) cin >> a[i];
 
	ll MOD = 1e9+7;
	ll dp[2][k+1];
	// dp[i%2][j] : i-1番目の子供で飴がj個余るときの分け合う方法数
	rep(i, 2) rep(j, k+1) dp[i][j] = 0;
	dp[0][k] = 1;
	for(int i = 0; i < n; i++){
		dp[(i+1)%2][k] = dp[i%2][k];
		for(int j = k-1; j >= 0; j--){
			if(j >= k-a[i]){
				dp[(i+1)%2][j] = dp[(i+1)%2][j+1] + dp[i%2][j];
				dp[(i+1)%2][j] %= MOD;
			}
			else{
				dp[(i+1)%2][j] = dp[(i+1)%2][j+1] + dp[i%2][j];
				dp[(i+1)%2][j] %= MOD;
				dp[(i+1)%2][j] += MOD - dp[i%2][j+1+a[i]];
				dp[(i+1)%2][j] %= MOD;
			}
		}
	}
 
	cout << dp[n%2][0] << endl;
}