JOI '12 春合宿１：3 - 日本情報オリンピック旗
問題
https://www.ioi-jp.org/camp/2012/2012-sp-tasks/2012-sp-day1.pdf
解法
旗は再帰的に決まっていくので，
dp(x1, y1, x2, y2) := マス (x1, y1), (x2, y2) の正方形を旗にするときの最小コスト
と DP の漸化式を立てる．DP 内では「どの区画を一つレベルが下の旗にするか」，「他の区画はどの文字で統一するか」を全通り試せばよい．ここで，ある区画を一つレベルが下の旗にすると決めたとき，もしこのある区画が全て空きマスであればコストは自明に０になる．よって，この時は DP を呼び出す必要がないので枝刈りができて計算量を改善できる（2^30 四方のマスであっても制約より高々 1000 マスしか埋まっていないため）．O(K^4 * N) に枝狩りをするので実際はもっと小さい．
解答
枝刈りを思いつくまで 3 TLE してしまった．DP でこれ以上計算量が落とせないと感じたときに，DP の結果が自明なケースは枝刈りすることによって計算量を落とすことは重要だと思った．
