题解归档 - cf1198D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf1198D
• 本地来源：problems/cf1198D/idea.md
• 题目链接：https://codeforces.com/contest/1198/problem/D
• 原始标题：1198D — Rectangle Painting 1

思路

1198D — Rectangle Painting 1

题意

$n\times n$ 网格，. 白 # 黑。一次可选任意子矩形全部染白，代价为 $\max(h,w)$。求全部染白的最小总代价。$n\le 50$。

做法

四维区间 DP（记忆化搜索）：

• $f(x_1,y_1,x_2,y_2)$：矩形 $(x_1,y_1)$–$(x_2,y_2)$ 染白的最小代价。
• 单格：$f=1$ 若 #，否则 $0$。
• 否则初始取「整块矩形一次染白」代价 $\max(x_2-x_1+1,\,y_2-y_1+1)$。
• 枚举水平/竖直切分，$f=\min(f,\,f_{\text{上}}+f_{\text{下}})$ 或 $f_{\text{左}}+f_{\text{右}}$。

复杂度 $O(n^4\cdot n)$，$n=50$ 可过。

实现注意

递归 dfs 内必须用局部变量存当前最优值与循环下标；若复用 main 里的全局 ans/i，递归会互相覆盖，样例会 WA。

Catalog 备注

catalog_priority.json 中本条误标为「二维 BIT / Rectangle Painting II」；1198D 是区间 DP（Painting 1，代价 $\max$）。二维树状数组对应 1198E（Painting 2，代价 $\min$，坐标压缩 + 2D BIT）。已应将 Catalog 缺口改指 1198E。

验证

• 样例 sample.in → 3
• stress.py -n 100 与 brute.cpp（同 DP 记忆化）一致

代码

来源：problems/cf1198D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 02:48:39
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=55;
ll dp[maxn][maxn][maxn][maxn],n,i,j,k;
char s[maxn][maxn];
ll dfs(ll x1,ll y1,ll x2,ll y2){
    ll u,v,cur;
    if(dp[x1][y1][x2][y2]!=-1) return dp[x1][y1][x2][y2];
    if(x1==x2 and y1==y2) return dp[x1][y1][x2][y2]=(s[x1][y1]=='#');
    cur=max(x2-x1+1,y2-y1+1);
    for(u=x1;u<x2;u++) cur=min(cur,dfs(x1,y1,u,y2)+dfs(u+1,y1,x2,y2));
    for(v=y1;v<y2;v++) cur=min(cur,dfs(x1,y1,x2,v)+dfs(x1,v+1,x2,y2));
    return dp[x1][y1][x2][y2]=cur;
}
int main(){
    cin>>n;
    for(i=1;i<=n;i++) scanf("%s",s[i]+1);
    memset(dp,-1,sizeof(dp));
    cout<<dfs(1,1,n,n)<<"\n";
    return 0;
}