There is a square grid of size n×nn \times n. Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs max(h,w)\max(h, w) to color a rectangle of size h×wh \times w. You are to make all cells white for minimum total cost.

大致题意 📖

有一个n×nn \times n的矩阵,其中有mm 个黑块,其余为白块,你可以选择一个n×mn \times m矩阵,将其染成白色,费用为max(n,m)max(n,m),求将涂染成全白的最小费用

链接 🔗

「CodeForces 1198D」 Rectangle Painting 1

题解 ❓

动态规划O(n4)O(n^4),枚举每块矩阵的长宽,进行切割求最小值
一种比较优美的实现 SC.ldxcaicai

代码

const ll maxd = 55;
ll a[maxd][maxd],dp[maxd][maxd][maxd][maxd];
char s[maxd];
ll dfs(ll x1,ll y1,ll x2,ll y2)
{
    if(dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2]; // 存在值时
    if(x1 > x2  || y1 > y2) return dp[x1][y1][x2][y2]=0; // 边界
    if(x1 == x2 && y1 == y2) return dp[x1][y1][x2][y2] = a[x1][y1]; // 1*1矩阵
    ll now = max(x2-x1+1,y2-y1+1); //全部涂的价值
    FOR(a,x1,x2-1) now = min(now,dfs(x1,y1,a,y2) + dfs(a+1,y1,x2,y2));   // 枚举宽
    FOR(a,y1,y2-1) now = min(now,dfs(x1,y1,x2,a) + dfs(x1,a+1,x2,y2)); // 枚举长
    return dp[x1][y1][x2][y2] = now;
}
int main()
{
//    __IN;__OUT;
    ll n; RLL(n);
    FOR(i,1,n)
    {
        RS(s+1);
        FOR(j,1,n) a[i][j] =  ( s[j]  == '#');
    }
    memset(dp,-1,sizeof(dp));
    PLN(dfs(1,1,n,n));
    return 0;
}