たとえ簡単な DP でも一発で通ると嬉しいよね。
問題概要
原文 → Equal Sum Sets | Aizu Online Judge
以下の相異なる自然数 個の合計が となる組み合わせの総数を求めよ。
解説
以下の各数字 について、 を使うときと使わないときを考えてみます。
- を使うときは、合計が 増え、使う数字の数は 増える
- を使わないときは、合計は変わらず、使う数字の数も変わらない
これを用いて DP を書きます。計算量 です。
ソースコード
signed main() { int N, K, S; while(cin >> N >> K >> S, N || K || S) { // dp[i][j][k] := i 以下の数字を j 個使って k を作る組み合わせ int dp[25][25][255] = {}; dp[0][0][0] = 1; repq(i,1,N) { repq(j,0,K) { repq(k,0,S) { // i を使うと 合計は i 増える if(k - i >= 0 && j != 0) dp[i][j][k] += dp[i-1][j-1][k-i]; // i を使わないと 合計は変わらない dp[i][j][k] += dp[i-1][j][k]; } } } cout << dp[N][K][S] << endl; } return 0; }
にしてもAOJ-ICPCでこれ150点なのかー。・・・と思ってたけどよく考えたら が20までしかないからビットで全列挙できるか。