TDPC (Typical DP Contest) A - コンテスト

部分和問題とほとんど一緒なのだけど、意外と詰まるかもしれない。

• 問題へのリンク

問題概要

個の正の整数 の中からいくつか選んで総和をとる。作ることのできる整数が何通りあるか求めよ。

制約

• 
• 

考えたこと

この問題とよく似た部分和問題とは次のような問題である。

---

個の正の整数 の中からいくつか選んで総和をとった値を にできるかどうかを判定せよ

---

この問題に対しては次のような配列 dp を定義することで解くことができる。

• ← 個の整数のうち最初の 個の整数の中からいくつか選んだ総和を にできるかどうか

遷移はこんな感じにできる ( の範囲に注意)。

dp[i][j] = true のとき
dp[i+1][j] = true;
dp[i+1][j+a[i]] = true;

今回の問題

今回の問題は、具体的な整数 を作れるかどうかを問うのではなく、作れる整数の個数を求める問題となっている。しかし部分和問題が解けていればほとんど解決済みである。なぜなら、部分和問題を解いて得られた配列 dp を用いることで、次の情報が得られる。

---

dp[N][j] をみることで、整数 を作れるかどうかがわかる。

---

よって、 について dp[N][j] が True であるような の個数を調べればよい。 の範囲を 10000 までとしたのは、, という制約から。

計算量は、作りうる最大の整数を として、 となる。

コード

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 入力
    int N; 
    cin >> N;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    // DP テーブル
    int W = 10000;
    vector<vector<bool>> dp(N+1, vector<bool>(W+1, false));
    dp[0][0] = true;

    // ループ
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= W; ++j) {
            if (!dp[i][j]) continue;
            dp[i+1][j] = true;
            if (j+a[i] <= W) dp[i+1][j+a[i]] = true;
        }
    }

    // 答え
    int res = 0;
    for (int j = 0; j <= W; ++j) {
        if (dp[N][j]) ++res;
    }
    cout << res << endl;
}