mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ CodeForces 問題 codeforces.com 解法 落ち着いて dp すれば良いです。dp[n][m][k] = (n*m の長方形で, ぴったり k 個の square を作るには最低いくつのコストが必要か？) を考えます。分割の仕方は 縦に切るか横に切るかしかなく, 2 つに分割した長方形に対して, 一方で kk 個の square を担当したとすると, もう一方は k-kk 個の square を担当することになります。これらをしっかり場合分けして, コストが一番小さいものを求めれば良いです。 int dp[33][33][55]; int dfs(int n, int m, int k) { i… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F02%2F09%2F231102" title="Educational Codeforces Round 1 E. Chocolate Bar - mayoko’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2016-02-09 23:11:02 rich https://mayokoex.hatenablog.com/entry/2016/02/09/231102 1.0 100%