No.005 D

クエリに対して $O(1)$ で計算できるよう, 前処理をする.

左上を $(x, y)$, 右下を $(x+u, y+v)$ とする矩形内のたこ焼きのおいしさの合計を $S(x, y, u, v)$ とする. 当然, $S(x, y, 0, 0) = D_{yx}$ である.

この $S(x, y, u, v)$ を動的計画法で埋めていく.

まずは $S(x, y, u, 0)$ を考えると,

$$S(x, y, u, 0) = S(x, y, u-1, 0) + S(x+u, y, 0, 0)$$

となるので, この式にしたがって更新していく.

次に $S(x, y, u, v)$ を考えると,

$$S(x, y, u, v) = S(x, y, u, v-1) + S(x, y+v, u, 0)$$

となるので, 同様に更新していく.

面積が $p$ のときのたこ焼きのおいしさを $T(p)$ として, $S(x, y, u, v)$ を更新するときに $T((u+1)(v+1))$ も同時に更新していく.

求めたいのは $\min_{q \leq p} T(q)$ なので, これもあらかじめ計算しておく.