JOI 09春合宿 abduction(難易度8)
x軸方向とy軸方向に分けて考える. するとx軸方向について最終的な(正負を考えた)移動距離の和が$ W, y軸方向については$ Hであればよいことがわかる. よってこれらを分けて考え, 最終的にその条件を満たす組の数を掛けることにより解ける. では, x軸方向飲みについて考えてみる(y軸方向についても同様に処理できる). $ Xが左と右のどちらを向いているか分かれば, 例えば$ A_1 - A_2 + A_3 + A_4 - A_5 = Wのように左なら負, 右なら正とした条件式に変形できる. ここで$ dp_{i, j} := $ i番目まで見て, 和が$ jの場合の数 としてDPをしていくことを考える. すると$ O(W^3)のDPを書くことによってこの問題を解くことができた. しかしこれだとまだ不十分である. そこで累積和を用いてDPの計算を高速化すると, $ O(W^2)で解くことができる.