BZOJ3810:[Coci2015]Stanovi dp

思路:

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

无脑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;
}