记忆化搜索,其实思路不太难吧,但是优化比较难想,建议评蓝。
题意简述:
有一个 $m\times n$ 的方格矩阵,把这个矩阵分为若干部分,且要求每一个矩阵都要与边界相邻。令 $k$ 为标准面积,不满意度为{所有矩阵面积减去 $k$ 的平方}之和。求最小的不满意度。
搜索
lg 题库里有道题叫生日快乐(这道题是蓝的,但是难度严重虚高,个人觉得最多是绿),其实思路相仿,不过这题要难一些。
我们假设拿到了一个已知所有信息、且满足四周有边界的矩阵,我们要对它进行搜索。
首先我们要解决传参问题:什么算已知条件,而且如何判断这个矩阵是不是满足条件呢?
首先长和宽是有必要的。而且因为这道题要求每一个矩阵都要挨着边界,所以我们需要知道它四面挨着边界的情况。
dfs 函数中传 $6$ 个参数:
int
类型:$x$ (矩阵的长),$y$ (矩阵的宽)。bool
类型:up
(此矩阵上面那条边是否挨着边界),down
(下面那条边是否挨着边界),left
(左边那条边是否挨着边界),right
(右边那条边是否挨着边界)。
解决完了 dfs 函数的传参问题,那怎么搜索呢?
我们先来分析出口。
由于题目要求,只要已知一个矩阵四面都没挨着边界,就直接返回一个极大值。
对于一个满足条件且已知的矩阵,有两种思路:
直接把它作为一个最终划分的矩阵;
把它继续分成更小的矩阵。
第一种思路很好解决,直接按照长、宽求就行了。
关键是第二种。
为了方便大家理解,我随便画了一个矩阵举例说明:
(Excel 真好用啊,蓝色为边界的外面那一圈)
对于这个矩阵,我们又有两种划分的方法:
- 横着切;
(红色的地方就是能切的地方。)
- 竖着切。
那我们只需要分两种情况,分别枚举切割的地方,寻找最小值就可以了。(比如说,枚举上面/左边那个矩阵的长/宽)
最后再看一下哪种情况会更好。
注意一个细节:横着切需满足 $x>1$,竖着切需满足 $y>1$。
核心代码大概长这样:
1 | if(!(up||down||left||right)) return inf; //不沿海 |
记忆化
开一个六维的数组 $dp$,每一维都对应一个传的参数,把 dfs 的值存在里面即可。
这个时候有人就会说了:可是不一样的矩阵可能六个参数都一样,那这个如何判断?
答案是不需要判断。虽然的确这种情况是存在的,但是,如果六个参数都一样,算出来的结果肯定也一样,这不会影响结果,还会减小运行的时间。
剪枝
- 可行性剪枝
观察一下上面的图,不难发现,有一些情况是不能做横着或者竖着的分割的,比如说这种:
这个东西就不能竖着切,因为如果竖着切了,左边的那个矩阵就不挨着边界了。
那我们可以写出矩阵要横着切和竖着切的条件:
横着:
up&&down||left||right
竖着:
left&&right||up||down
为什么呢?以横着切举例:
现在四面是否挨着边界不知道。
如果要求成功,就必须满足下列至少一个条件:
上面和下面都挨着边界。
左边挨着边界,或者右边挨着边界。
你们自己去想一想,竖着也类似。
- 最优性剪枝
很好想,要是一个矩阵的面积小于 $k$,就不继续切了,直接返回。
- 等价性剪枝
zszz 矩阵是可以转的对吧?
拿到一个矩阵之后,我们可以尝试把它转一下:可以向左旋转 $0^{\circ},90^{\circ},180^{\circ},270^{\circ}$,每一种旋转都可以查看是否已求出结果,如果有,直接返回。
代码比较简单,但是思考的过程比较绕:
1 | if(dp[x][y][up][down][left][right]!=-1) return dp[x][y][up][down][left][right]; //正常 |
剪枝就这三个。虽然不多,但足以通过这道题。
最后再卡一下常。
Code
1 |
|
这个人是个不可爱的 BUG 制造机,不过 TA 还是很喜欢瞎搞。
祝您拥有愉快的一天~