思路:

首先有一个性质:当前的矩形必定可以被划分成两个子矩形.

无脑dp.

记录四个状态表示当前矩形的四条边是不是原来的大矩形的边.

然后记忆化搜索即可.

(要非常注意常数优化)

#include
#include
#include
#include
#include
#include
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;i0&&b;+c+d>0)
        for(int i=1;i