一道简单的DP，虽然用搜索写的。我们用f(i,j,z)表示把X×Y的巧克力分成总大小为Z的小块所需最小代价。每次掰开的方式有两种，横着掰和竖着掰，故有两种转移。
#include<bits/stdc++.h> using namespace std; int n,m,k,T; const int inf=0x3f3f3f3f; typedef long long ll; int a[53][53][75]; int f(int x,int y,int z){ if(!z||x*y==z) return 0; if(a[x][y][z]) return a[x][y][z]; int res=inf; for(int i=1;i<=y-i;i++){ for(int j=0;j<=z;j++){ res=std::min(res,x*x+f(x,i,j)+f(x,y-i,z-j)); } } for(int i=1;i<=x-i;i++){ for(int j=0;j<=z;j++){ res=std::min(res,y*y+f(i,y,j)+f(x-i,y,z-j)); } } return a[x][y][z]=res; } int main(){ cin>>T; while(T--){ scanf("%d%d%d",&n,&m,&k); printf("%d\n",f(n,m,k)); } return 0; }