链接: https://codeforces.com/contest/1199/problem/F
题面:
There is a square grid of size n×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×w. You are to make all cells white for minimum total cost.
The first line contains a single integer n (1≤n≤50) — the size of the square grid.
题意: 给你一个n*n的矩形，里面有黑色，白色，问你要将黑色涂成白色的最小花费，若所涂小矩形长宽为w,h，则花费为max(h,w)；
思路: 我们意识到n很小，开个n^4都绰绰有余，我们意识到可以枚举每个子矩形，也就是爆搜，所以我们可以进行记忆化搜索，不断将一个大矩形切开变成小矩形，直到单独涂一格

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=55;
char mp[N][N];
int dp[N][N][N][N];
vector<int>ma;
int dfs(int a,int b,int x,int y)
{
	if(a==x&&b==y)
		return (mp[x][y]=='#');
	if(dp[a][b][x][y]!=-1)
		return dp[a][b][x][y];
	dp[a][b][x][y]=max(x-a,y-b)+1;
	for(int i=a;i<x;i++)
		dp[a][b][x][y]=min(dp[a][b][x][y],dfs(a,b,i,y)+dfs(i+1,b,x,y));
	for(int i=b;i<y;i++)
		dp[a][b][x][y]=min(dp[a][b][x][y],dfs(a,b,x,i)+dfs(a,i+1,x,y));
	return dp[a][b][x][y];
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%s",mp[i]);
	memset(dp,-1,sizeof dp);
	cout<<dfs(0,0,n-1,n-1)<<endl;
	return 0;
}