There is a square grid of size . 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 to color a rectangle of size . You are to make all cells white for minimum total cost.
大致题意 📖
有一个的矩阵,其中有 个黑块,其余为白块,你可以选择一个矩阵,将其染成白色,费用为,求将涂染成全白的最小费用
链接 🔗
「CodeForces 1198D」 Rectangle Painting 1
题解 ❓
动态规划,枚举每块矩阵的长宽,进行切割求最小值
一种比较优美的实现 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;
}