yukicoder 269 - 見栄っ張りの募金活動

これは良い問題だ!🤠✨

類題
creep06.hatenablog.com

問題

n人のクラスで募金を計s円集めて寄付することにした
生徒は出席番号順に寄付金額を決めていく
生徒は皆見栄っ張りなので、出席番号が1つ前の生徒よりk円以上高い金額を寄付しないと気が済まない
不満な生徒が現れることなくクラスの合計寄付金額がちょうどs円になるような各生徒の寄付金額の組み合わせは何通りあるか

2 <= n <= 100
0 <= s <= 20000
0 <= k <= 100

解法

生徒i以降は最低(k=0)でも生徒iと同額を寄付する
∴ 生徒iが1円多く払うことにすると、それ以降の生徒も全員最低1円多く払わないといけなくなる
∴ 合計寄付金額がn-i円増えることが確定する
これが重要な考察

dp[i][j]: 生徒iまでの金額が決定しており、合計寄付金額のうち↑で確定した額がj円であるような組み合わせ数
とすると遷移は
dp[i][j] = dp[i-1][j-k(n-i)] + dp[i][j-(n-i)]
となる
dp[i-1][j-k(n-i)]: 生徒iが生徒i-1よりちょうどk円多く寄付するケース
dp[i][j-(n-i)]: 生徒iが寄付金を1円増やすケース

int n, s, k, dp[101][20020];

signed main() {
	cin >> n >> s >> k;
	dp[0][0] = 1;
	rep(i,n) rep(j,s+1) {
		if (i && j-k*(n-i)>=0) (dp[i][j] += dp[i-1][j-k*(n-i)]) %= mod;
		if (j-(n-i)>=0) (dp[i][j] += dp[i][j-(n-i)]) %= mod;
	}
	cout << dp[n-1][s] << endl;
}