yukicoder 269 - 見栄っ張りの募金活動
これは良い問題だ!🤠✨
問題
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; }