トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

動的計画法(桁DP)

[アルゴリズム,DP]

動的計画法(桁DP)

  問題設定

から、動的計画法による桁DPを学びましょう。

  解説

A以下の非負整数の総数を求める

  • C言語のHack的な成分が薄まったのでは?
    • C言語にはbool型が無いので0がfalseになる、0以外はtrue
  • 謎のパイプ
    • dp[i + 1][j ll d < lim] の部分が読み取りづらいのだが ||は論理和なので、上の0がfalseになる話と合わせて考えると
    • if not j.zero? or d<lim then 1 else 0 end みたいに書き換えられる
lines = <<'EOS'
4275631
EOS

#lines = $stdin.read
array = lines.split("\n")
A = array[0].split("").map(&:to_i)
N = array[0].to_s.length

MOD = 1_000_000_007
dp = Array.new(101010).map{Array.new(2, 0)} # pos, less
dp[0][0] = 1

for i in 0...N
  for j in 0...2
    lim = j.zero? ? A[i] : 9
    for d in 0...lim+1
      less = if not j.zero? or d<lim
               1
             else
               0
             end
      dp[i+1][less] += dp[i][j]
    end
  end
end

ans = 0
for j in 0...2
  ans += dp[N][j]
end

puts ans

A以下の非負整数のうち、3の付く数の総数を求める

# coding: utf-8
lines = <<'EOS'
4275631
EOS

#lines = $stdin.read
array = lines.split("\n")
A = array[0].split("").map(&:to_i)
N = array[0].to_s.length

MOD = 1_000_000_007
dp = Array.new(101010).map do
  Array.new(2).map do
    Array.new(2, 0)
  end
end # pos, less, has3
dp[0][0][0] = 1

for i in 0...N
  for j in 0...2
    for k in 0...2
      lim = j.zero? ? A[i] : 9
      for d in 0...lim+1
        less = if not j.zero? or d<lim
                 1
               else
                 0
               end
        has3 = if not k.zero? or d == 3
                 1
               else
                 0
               end
        dp[i+1][less][has3] += dp[i][j][k]
      end
    end
  end
end

ans = 0
for j in 0...2
  ans += dp[N][j][1]
end

puts ans

A以下の非負整数のうち、「3が付くまたは3の倍数」の数の総数を求める

A以下の非負整数のうち、「3が付くまたは3の倍数」かつ「8の倍数でない」数の総数を求める

お名前: コメント: