TDPC A コンテスト
続き。
初めのコード
n = int(input()) p = [int(i) for i in input().split()] ans = set() v = 0 def rec(i): global v if i == n: ans.add(v) return v += p[i] rec(i+1) v -= p[i] rec(i+1) rec(0) print(len(ans))
単純に、引数を減らしてみた。 で、漸化式を立てる。
dp[i+1][j] := i 番目までで j ができるかどうか
この漸化式を立てると、
dp[i+1][j] = dp[i][j] || dp[i][j-p[i]] ただし、dp[0][0] = True
となる。 よって、これをそのままコードにすれば良い。
n = int(input()) p = [int(i) for i in input().split()] dp = [[False for j in range(sum(p)+1)] for i in range(n+1)] dp[0][0] = True for i in range(n): for j in range(sum(p)+1): dp[i+1][j] = dp[i][j-p[i]] or dp[i][j] ans = 0 for i in range(sum(p)+1): if dp[n][i]: ans += 1 print(ans)
計算量は、O(n * sum(p)) なので、10の6乗ぐらいになって実行可能。
もっと早く漸化式を立てられば、いいかなぁと思った。