There is a square grid of size $n \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)$ to color a rectangle of size $h \times w$. You are to make all cells white for minimum total cost.

链接 🔗

「CodeForces 1198D」 Rectangle Painting 1

代码

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