Educational Codeforces Round1 E - Chocolate Bar - かんプリンの学習記録

問題概要
思考の流れ
提出プログラム
感想

問題概要

${n×m(1\le n,m\le 30)}$ の正方形のチョコからなる長方形の板チョコがあり, その板チョコを縦横に割っていく. 割るときにかかるコストは割る長さの2乗であり, ちょうど ${1\le k\le \min(n×m,50)}$ この正方形のチョコに分割したい. そのように分割するときの最小コストを求めよ.

上のような質問が ${1\le t\le 40910}$ 個与えられる.

思考の流れ

制約が小さいが質問が多いので各質問に対して高速に答えるか, 前計算でいっきに求めたい. チョコを割るとサイズの小さな別の問題になるので前計算ですべて求めることができそう.
DPでやる. ${dp[i][j][k]}$ を「 ${i×j}$ の板チョコを ${k}$ 個の正方形に分割するときの最小コスト」とすると更新式は以下のようになる.