AOJ 1176 - 輪番停電計画 - ツバサの備忘録

解法

はじめに、2次元累積和を用いて、ある長方形の範囲の需要の合計を $O(1)$ で求めることができるようにしておきます。
ここから、DPを行います。
$dp[i][j][k][l] =$ 長方形の左上が $(i,k)$ ,右下が $(j,l)$ となるような範囲のグループの分け方の最適解
とします。最適解、なのでグループ数と予備力の2つの情報を持ち、グループ数、予備力、の優先順位でより値が大きいものが最適解となります。

そもそもですが、左上が $(i,k)$ ,右下が $(j,l)$ となるような範囲を停電させても供給力が足りない場合、すなわち $s-(与えられた町全体の需要)+(今見ている範囲の需要の合計) \lt 0$ ならば、答えはありません。
それ以外の場合を見ていきます。
答えの候補ですが、

今見ている範囲をこれ以上分割しない
今見ている範囲をある縦線で区切る
今見ている範囲をある横線で区切る

の3パターンになります。全ての候補を調べ上げ、その中での最適解を選べばよいです。
一番最初のパターンは、グループ数がもちろん0、予備力は $s-(与えられた町全体の需要)+(今見ている範囲の需要の合計)$ そのものです。
また、2つめのパターンと3つめのパターンでは、縦横が異なるのみで操作自体は同じなので、今回は横線で区切るパターンを見ていきます。
左上が $(i,k)$ ,右下が $(j,l)$ となっている範囲を横線で区切ると、
左上が $(i,k)$ ,右下が $(x,l)$ と、左上が $(x+1,k)$ ,右下が $(j,l)$
の2つの範囲に分割されます。
まずは、それぞれの範囲の最適解を調べます。これは、再帰的に調べればよいです。
あとは、2つに分けた範囲それぞれのグループ数の和と、2つに分けた範囲それぞれの予備力のうち小さい方をセットにすれば、今見ている左上が $(i,k)$ ,右下が $(j,l)$ の範囲の答えの候補になります。