CF1198D Rectangle Painting 1

一道难度虚高的平面dp题，想出状态后问题便迎刃而解

题解：

设$f[x1][y1][x2][y2]$表示填满以$(x1,y1)$为左上角，以$(x2,y2)$为右下角矩形的最小代价，这显然是有可加性的，于是我们可以将它拆成左右或上下两个子矩形进行子问题求解，分割点可以暴力枚举

递归边界是当只剩一个1x1的矩形时，可以直接返回它是否需要覆盖

复杂度：状态四维，枚举一维，套起来总共$O(n^5)$

由于复杂度很宽松，我们可以用记忆化搜索简单的实现代码

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=55;
int f[N][N][N][N],n;
char c[N][N];

int dp(int x,int y,int xx,int yy){
    int &now=f[x][y][xx][yy];
    if(~now) return now;
    now=max(xx-x+1,yy-y+1);
    if(x==xx&&y==yy){ //递归边界
        if(c[x][y]=='.') now=0;
        return now;
    }
    for(int i=x;i<xx;i++) //分成上下两个
        now=min(now,dp(x,y,i,yy)+dp(i+1,y,xx,yy));
    for(int i=y;i<yy;i++) //分成左右两个
        now=min(now,dp(x,y,xx,i)+dp(x,i+1,xx,yy));
    return now;
}

signed main(){
    read(n);
    for(int i=1;i<=n;i++) scanf("%s",c[i]+1);
    memset(f,-1,sizeof f);
    write(dp(1,1,n,n));
}