Educational Codeforces Round 1 E. Chocolate Bar
解法
落ち着いて 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) { int& ret = dp[n][m][k]; if (ret >= 0) return ret; if (k == 0 || k == n*m) return ret = 0; if (k > n*m) return ret = 100000000; if (n == 1 || m == 1) return ret = 1; ret = 1000000; if (k < n) ret = min(ret, n*n+1); for (int i = 1; i < m; i++) { for (int kk = 0; kk <= k; kk++) { ret = min(ret, n*n + dfs(n, m-i, kk) + dfs(n, i, k-kk)); } } if (k < m) ret = min(ret, m*m+1); for (int j = 1; j < n; j++) { for (int kk = 0; kk <= k; kk++) { ret = min(ret, m*m + dfs(n-j, m, kk) + dfs(j, m, k-kk)); } } return ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); int t; cin >> t; memset(dp, -1, sizeof(dp)); while (t--) { int n, m, k; cin >> n >> m >> k; cout << dfs(n, m, k) << endl; } return 0; }