思路:
首先有一个性质:当前的矩形必定可以被划分成两个子矩形.
无脑dp.
记录四个状态表示当前矩形的四条边是不是原来的大矩形的边.
然后记忆化搜索即可.
(要非常注意常数优化)
#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 1ll<<60
#define N 310
long long f[2][2][2][2][N][N];
int n,m,k;
inline long long calc(int w,int h,int a,int b,int c,int d){
if(w>h){
swap(w,h);
int aa=c,bb=d,cc=b,dd=a;
a=aa,b=bb,c=cc,d=dd;
if(a>b)swap(a,b);
if(c>d)swap(c,d);
}
if(f[a][b][c][d][w][h]!=-1)return f[a][b][c][d][w][h];
if(!a&&!b&&!c&&!d)return f[a][b][c][d][w][h]=INF;
long long re=(long long)(w*h-k)*(w*h-k);
if(a+b+c>0&&a+b+d>0)
for(int i=1;i<w;++i)re=min(re,calc(i,h,a,b,c,0)+calc(w-i,h,a,b,0,d));
if(a+c+d>0&&b+c+d>0)
for(int i=1;i<h;++i)re=min(re,calc(w,i,a,0,c,d)+calc(w,h-i,0,b,c,d));
return f[a][b][c][d][w][h]=re;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
register int i,j;
memset(f,-1,sizeof f);
printf("%lld",calc(n,m,1,1,1,1));
return 0;
}