🐸
[EDPC C] Vacation
難しめのDP問題。
例1で問題を理解する
1〜3日目までに A B C のどの活動をしたら幸福度が最大になるか？
| A | B | C | |
|---|---|---|---|
| 1日目 | 10 | 40 | 70 |
| 2日目 | 20 | 50 | 80 |
| 3日目 | 30 | 60 | 90 |
これはひと目 C → C → C の 70 + 80 + 90 = 240 がもっとも幸福度が高くなるように見えるが、連続で同じ活動をしちゃいけないので、二日目はしかたなく B を選んで、C → B → C の 70 + 50 + 90 = 210 が答えになる。
解説を元にした実装 (AC)
228 ms
N = gets.to_i # => 3
ABC = N.times.collect { gets.split.collect(&:to_i) } # => [[10, 40, 70], [20, 50, 80], [30, 60, 90]]
W = ABC.first.size # => 3
dp = Array.new(N.next) { Array.new(W, 0) } # => [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
(1..N).each do |y|
W.times do |x|
W.times do |i|
if i == x
next
end
if dp[y][x] < dp[y - 1][i] + ABC[y - 1][x]
dp[y][x] = dp[y - 1][i] + ABC[y - 1][x]
end
end
end
end
p dp[N].max # => 210
| A | B | C | |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 10 | 40 | 70 |
| 2 | 90 | 120 | 120 |
| 3 | 150 | 180 | 210 |
たとえば dp[2] の行では ABC は 20 50 80 なので、一つ上の 10 40 70 からそれぞれを足すと、
| 10 | 40 | 70 | |
|---|---|---|---|
| 20 | 10 + 20 = 30 | 40 + 20 = 60 | 70 + 20 = 90 |
| 50 | 10 + 50 = 60 | 40 + 50 = 90 | 70 + 50 = 120 |
| 80 | 10 + 80 = 90 | 40 + 80 = 120 | 70 + 80 = 150 |
となるが、連続で同じ活動ではできない (たとえば dp[2][A] は同じ ABC の A が使えない) ので、
| 10 | 40 | 70 | |
|---|---|---|---|
| 20 | 40 + 20 = 60 | 70 + 20 = 90 | |
| 50 | 10 + 50 = 60 | 70 + 50 = 120 | |
| 80 | 10 + 80 = 90 | 40 + 80 = 120 |
クロスした部分の計算は使えず、いいとこどりで 90 120 120 になる、ということか。書いてて頭がこんがらがってくる。
リファクタリング (AC)
W.times do |i|
W.times do |j|
i == j and next
[i, j] # => [0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1]
end
end
は、
W.times.to_a.permutation(2).to_a # => [[0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1]]
と書けるので、
226 ms
N = gets.to_i # => 3
ABC = N.times.collect { gets.split.collect(&:to_i) } # => [[10, 40, 70], [20, 50, 80], [30, 60, 90]]
W = ABC.first.size # => 3
dp = Array.new(N.next) { Array.new(W, 0) } # => [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
WA = W.times.to_a # => [0, 1, 2]
(1..N).each do |y|
WA.permutation(2) do |x, i|
dp[y][x] = [dp[y][x], dp[y - 1][i] + ABC[y - 1][x]].max
end
end
p dp[N].max # => 210
でもいい。が、冗長に書いた方がわかりやすい気もする。
Discussion