记忆化搜索
设计状态dp(i,j,k)表示长宽分别为i和j的矩阵,取出k块蛋糕的费用,然后枚举第一刀的切割点
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
const int inf = 0x3f3f3f3f;
int dp[N][N][N * N];
int dfs(int n, int m, int sum)
{
if (dp[n][m][sum] != inf)
return dp[n][m][sum];
if (n * m == sum || !sum)
return dp[n][m][sum] = 0;
for (int i = 1; i < n ; i++)
if(m*i<=sum)
dp[n][m][sum] = min(dp[n][m][sum], dfs(n - i, m, sum - m * i) + m * m);
else
dp[n][m][sum] = min(dp[n][m][sum], dfs(i, m, sum) + m * m);
for (int i = 1; i < m; i++)
{
if (i * n <= sum)
dp[n][m][sum] = min(dp[n][m][sum], dfs(n, m - i, sum - n * i) + n * n);
else
dp[n][m][sum] = min(dp[n][m][sum], dfs(n, i, sum) + n * n);
}
return dp[n][m][sum];
}
int main()
{
int t;
cin >> t;
memset(dp, 0x3f, sizeof dp);
dp[0][0][0] = 0;
while (t--)
{
int n, m, k;
cin >> n >> m >> k;
cout << dfs(n, m, k) << "\n";
}
}