598E - Chocolate Bar - CodeForces Solution

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define x first
#define y second
#define endl '\n'
#define int long long
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int, int> PII;
const int N = 1e6 + 10;
const int M = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const double INFF = 0x7f7f7f7f7f7f7f7f, Pi = acos(-1);
const int mod = 1e9 + 7;
int f[35][35][35 * 35];
// 在i * j中切割k的最小值
// 细节i * j和j * i是一样的
int n, m, k;

int dfs(int i, int j, int o)
{
    if (o == 0)
        return 0;
    if (i * j == o)
        return 0;
    int &res = f[i][j][o];

    if (f[i][j][o] != -1)
        return f[i][j][o];
    // if (f[j][i][o] != -1)
    //     return res = f[j][i][o];
    res = 1e18;
    for (int y = 1; y < j; y++) // 切割最边缘的相当于没切，不能转移
    {
        for (int c1 = 0; c1 <= o; c1++)
        {
            res = min(res, dfs(i, y, c1) + dfs(i, j - y, o - c1) + i * i);
        }
    }
    for (int x = 1; x < i; x++)
    {
        for (int c2 = 0; c2 <= o; c2++)
        {
            res = min(res, dfs(x, j, c2) + dfs(i - x, j, o - c2) + j * j);
        }
    }
    // f[j][i][o] = res;
    return f[i][j][o];
}

signed main()
{
    ios;
    int t;
    cin >> t;
    memset(f, -1, sizeof(f));
    while (t--)
    {
        cin >> n >> m >> k;

        cout << dfs(n, m, k) << endl;
    }
    return 0;
}
/*
stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/