AtCoder Beginer Contest 005 - D
- AtCoder Beginer Contest 005 - D おいしいたこ焼きの焼き方
- 四角形の中身を任意の大きさの長方形に分けて、その中身を合計しておく
- また動的計画法みたいです
解説
領域（長方形）ごとの最大の美味しさ度はどうやって求めるか？
(方針) 解説スライドより
- 右下まで必ず使う長方形を全通り列挙する O(n^2)
- その長方形の美味しさの合計を列挙する O(1)
- 各長方形を全通り列挙する O(n^4)
- その長方形の美味しさの合計を列挙する O(1)
全てのたこ焼きの数に対して、最大値が求められる
- 各長方形を全通り列挙する O(n^4)
- 長方形をすべて列挙？ここをまずどうするか、とりあえず 0...N までの配列を２つ用意してそれぞれに対して組み合わせを求めてみる
| + | サンプルコード | |
- 右下まで必ず使う長方形を全通り列挙する O(n^2)
- N-1を先に含ませておいて、それ以外を選んでくる
なんか、具体的な動的計画法の式が解説にないぞい！困るぞい！
満点解法の解説
(具体的な方針) 競技プログラミングをするんだよ - ABC#005 より
- 典型的な領域分割？分割統治？の問題です。子問題を解くことで大問題を解くことができ全パターンを高速に計算できます。
- dp[i][j][w][h] を座標(i~i+w,j~j+h)の領域で焼いたときのたこ焼きのおいしさの合計と定義する
- hについて
- h の取りうる値は N-i までのはず
- dp[i][j][0][h] = dp[i][j][0][h-1] + dp[i+h][j][0][0] ( 0 < h < N-i )
- wについて
- w の取りうる値は N-j までのはず
- dp[i][j][w][h] = dp[i][j][w-1][h] + dp[i][j+w][0][h] ( 0 < w < N-j )
(手順)
- 領域の最大値を保持する連想配列 max_v を用意する、KEYが領域の面積でVALが領域の価値（おいしさ）の合計値
- 1 x 1 の領域をすべて探索して、連想配列に領域面積＝１の場合の最大値を格納する
- O(N ^ 2)
- 1 x h, 1 x w の領域をすべて探索して、連想配列に領域面積＝1 x h, 1 x wの場合の最大値を格納する
- O(N ^ 2)
- h x w の領域をすべて探索して、連想配列に領域面積＝h x wの場合の最大値を格納する
- O(N ^ 4)
lines = $stdin.read
array = lines.split("\n")
N = array[0].to_i
D = array[1..N].map{|s| s.split(" ").map(&:to_i)}
Q = array[N+1].to_i
P = array[N+2..Q+N+1].map(&:to_i)
I = J = W = H = N
dp = Array.new(I).map{
Array.new(J).map{
Array.new(W).map{
Array.new(H, 0)
}
}
}
max_v = {}
for i in 0..N-1
for j in 0..N-1
dp[i][j][0][0] = D[i][j]
max_v[1] = dp[i][j][0][0] if max_v[1].to_i < dp[i][j][0][0]
end
end
for i in 0..N-1
for j in 0..N-1
for h in 1...N-i
dp[i][j][0][h] = dp[i][j][0][h-1] + dp[i+h][j][0][0]
max_v[h+1] = dp[i][j][0][h] if max_v[h+1].to_i < dp[i][j][0][h]
#puts "dp[#{i}][#{j}][0][#{h}] = #{dp[i][j][0][h]}"
end
for w in 1...N-j
dp[i][j][w][0] = dp[i][j][w-1][0] + dp[i][j+w][0][0]
max_v[w+1] = dp[i][j][w][0] if max_v[w+1].to_i < dp[i][j][w][0]
#puts "dp[#{i}][#{j}][#{w}][0] = #{dp[i][j][w][0]}"
end
end
end
for i in 0..N-1
for j in 0..N-1
for h in 1...N-i
for w in 1...N-j
dp[i][j][w][h] = dp[i][j][w-1][h] + dp[i][j+w][0][h]
max_v[(w+1)*(h+1)] = dp[i][j][w][h].to_i if max_v[(w+1)*(h+1)].to_i < dp[i][j][w][h].to_i
#puts "dp[#{i}][#{j}][#{w}][#{h}] = #{dp[i][j][w][h]}"
end
end
end
end
P.each do |ps|
puts max_v.select{|k,v| k <= ps}.max_by{|k,v| v}.last
end