hogecoder

tsutaj 競技プログラミングの記録

AOJ 1335: Equal Sum Sets

たとえ簡単な DP でも一発で通ると嬉しいよね。

問題概要

原文 → Equal Sum Sets | Aizu Online Judge

 n 以下の相異なる自然数  k 個の合計が  s となる組み合わせの総数を求めよ。

  •  1 \leqq n \leqq 20
  •  1 \leqq k \leqq 10
  •  1 \leqq s \leqq 155

解説

 n 以下の各数字  i について、 i を使うときと使わないときを考えてみます。

  •  i を使うときは、合計が  i 増え、使う数字の数は  1 増える
  •  i を使わないときは、合計は変わらず、使う数字の数も変わらない

これを用いて DP を書きます。計算量  O(nks) です。

ソースコード

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点なのかー。・・・と思ってたけどよく考えたら  n が20までしかないからビットで全列挙できるか。