Educational Codeforces Round 1 E. Chocolate Bar

問題

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) {
    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;
}