题目传送门https://vjudge.net/problem/CSES-1744#author=beyoursven

关于题意

Chat_gpt 的中文翻译是错的，不是长为 ，宽为  的矩形，而是一个  的矩阵。

解题思路

设  表示一个  的矩阵的最少操作次数。

易得：

然后，对于  的情况，我们分两种情况讨论：

1. 我们可以横向切割：

对于一个切割线 ，可以把这个矩形分成如下部分：

那么就是分成了  和  的两个矩形。

2. 我们可以纵向切割。

图就不画了，很容易可以得到可以分成  和  两个矩形。

代码

#include<bits/stdc++.h>
using namespace std;

int n,m;
int f[501][501];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	memset(f,0x3f,sizeof f);
	for(int len=1;len<=min(n,m);len++)
	{
		f[len][len]=0;
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(i==j)continue;
			for(int k=1;k<j;k++)
			{
				f[i][j]=min(f[i][j],f[i][k]+f[i][j-k]+1);
			}
			for(int k=1;k<i;k++)
			{
				f[i][j]=min(f[i][j],f[k][j]+f[i-k][j]+1);
			}
		}
	}
	cout<<f[n][m];
}