题意：
给定一个n m个方块组成的巧克力块，最终要吃到k个方块
有两种切的方式：
（n m）
1.横着切，成本是m m
2.竖着切，成本是n n
做法：
考虑记忆化搜索，使用dp[n][m][k]代表一个n*m的巧克力最后要得到k块所需要的最小成本
状态转移：把每一次切的动作看作是一次转移:
以n,m,k为例
1.横着切，那么每次的成本是mxm,此时k的获得可以这样表示,我们枚举一层j从0-k,j表示前面那部分获得的巧克力，从而k-j表示后面的部分获得的巧克力
2.竖着切，成本就是nxn,k的表示和横着切一样
点击查看代码
// Problem: E. Chocolate Bar
// Contest: Codeforces - Educational Codeforces Round 1
// URL: https://codeforces.com/contest/598/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Author: a2954898606
// Create Time:2023-11-29 14:53:30
//
// Powered by CP Editor (https://cpeditor.org)
/*
/\_/\
(o o)
/ \
// ^ ^ \\
/// \\\
\ |
\_____/
/\_ _/\
*/
#include<bits/stdc++.h>
#define all(X) (X).begin(),(X).end()
#define all2(X) (X).begin()+1,(X).end()
#define pb push_back
#define mp make_pair
#define sz(X) (int)(X).size()
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
using namespace std;
typedef long long unt;
typedef vector<long long> vt_unt;
typedef vector<int> vt_int;
typedef vector<char> vt_char;
template<typename T1,typename T2> inline bool ckmin(T1 &a,T2 b){
if(a>b){
a=b;
return true;
}
return false;
}
template<typename T1,typename T2> inline bool ckmax(T1 &a,T2 b){
if(a<b){
a=b;
return true;
}
return false;
}
namespace smart_math{
long long quickpow(long long a,long long b,long long mod=0){
long long ret=1;
while(b){
if(b&1)ret*=a;
if(mod)ret%=mod;
b>>=1;
a*=a;
if(mod)a%=mod;
}
if(mod)ret%=mod;
return ret;
}
long long quickmul(long long a,long long b,long long mod=0){
long long ret=0;
while(b){
if(b&1)ret+=a;
if(mod)ret%=mod;
b>>=1;
a=a+a;
if(mod)a%=mod;
}
if(mod)ret%=mod;
return ret;
}
long long ceil_x(long long a,long long b){
if(a%b==0)return a/b;
else return (a/b)+1;
}
}
using namespace smart_math;
const long long mod=1e9+7;
const long long N=310000;
const long long M=300;
int dp[60][60][60];
int dfs(int n,int m,int k){
if(n*m==k||k==0)return 0;
if(n>m)swap(n,m);
if(dp[n][m][k])return dp[n][m][k];
int minn=mod;
for(int i=1;i<=n/2;i++){
for(int j=0;j<=k;j++){
int ans=m*m+dfs(i,m,j)+dfs(n-i,m,k-j);
ckmin(minn,ans);
}
}
for(int i=1;i<=m/2;i++){
for(int j=0;j<=k;j++){
int ans=n*n+dfs(i,n,j)+dfs(m-i,n,k-j);
ckmin(minn,ans);
}
}
return dp[n][m][k]=minn;
}
int solve(){
int n,m,k;
cin>>n>>m>>k;
cout<<dfs(n,m,k)<<endl;
return 0;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
t=1;
cin>>t;
while(t--){
int flag=solve();
if(flag==1) YES;
if(flag==-1) NO;
}
return 0;
}