前言:
IOI 还出这样水的纯记忆化搜索题？还是 T4？真令人难以置信。
题意：
一个 N×M 的矩阵，对于任意一个子矩阵，只能横着或竖着分割，并且分割一次的价值为改子矩阵的元素之和，现要将该矩阵分割成 1×1 的方格，求最小的分割总价值之和。
思路：
看到这是个最优化的题，且数据范围很小，可以用搜索。
并且，对于一个相同的子矩阵，可能会搜到多次，由于它的最优值是一定的，所以可以用记忆化优化一下。
总结出搜索思路：
-
枚举是竖着切和横着切，以及切的位置。
-
继续递归，计算出切割后两个更小的子矩阵的价值，并求出所有切割方案中的最优值。
-
当搜索到的子矩阵大小为 1，直接返回。
-
当前子矩阵搜过，返回得出的最优值。
-
用最优值再加上当前子矩阵本身的和，即为该子矩阵的最优值。
对于子矩阵的和，可以用二维前缀和计算，优化时间。不知道二维前缀和的同学可以参考我的这篇博客。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[51][51];//读入的矩阵
int ans[51][51][51][51];//记忆化，记录最优值
bool f[51][51][51][51];//记忆化，记录搜没搜过
inline int dfs(int lx,int ly,int rx,int ry)
{
if(f[lx][ly][rx][ry]) return ans[lx][ly][rx][ry];//搜过直接返回最优值
f[lx][ly][rx][ry]=1;//否则先标记一下
if(lx==rx&&ly==ry)//大小为1，不需再切，直接返回
{
ans[lx][ly][rx][ry]=0;
return 0;
}
for(int i=lx;i<rx;i++)//横着切，以及切的位置
{
ans[lx][ly][rx][ry]=min(ans[lx][ly][rx][ry],dfs(i+1,ly,rx,ry)+dfs(lx,ly,i,ry)); //递归算值，并维护最优值
}
for(int i=ly;i<ry;i++)//竖着切，以及切的位置
{
ans[lx][ly][rx][ry]=min(ans[lx][ly][rx][ry],dfs(lx,i+1,rx,ry)+dfs(lx,ly,rx,i));//同上
}
ans[lx][ly][rx][ry]+=a[rx][ry]+a[lx-1][ly-1]-a[lx-1][ry]-a[rx][ly-1];//加上子矩阵自身，这里用了二维前缀和优化
return ans[lx][ly][rx][ry];//返回
}
int main()
{
cin>>n>>m;
memset(ans,0x3f,sizeof(ans));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];//二维前缀和预处理
}
}
printf("%d\n",dfs(1,1,n,m));
return 0;
}
写题解不易，点个赞呗。