2nm 块三明治, 每块是尺寸相同的等腰直角三角形, 拼成了 n*m 的矩形. 一块三明治能被吃掉仅当以下条件中的至少一个被满足:
- 它的斜边不与尚存的其他三明治相邻
- 它的两条直角边均不与尚存的其他三明治相邻
对于 i=1,2,...,n, j=1,2,...,m, 要吃掉 (i,j) 位置的两块三明治, 一共得吃掉多少块? (包括这两块本身)
- 35%: n,m ≤ 50
- 100%: n,m ≤ 400
一块三明治被吃掉, 会更新其他一些三明治的答案. 于是, 我想跑一发 SPFA......这样当然是不行的. 依赖的三明治的块数不具备可加性. 写完才发现. TAT 就丢了这个假算法上去......
不要从外围考虑啦! 从我们的目标着手. 先吃掉哪些三明治才能吃掉 (i,j) 呢? 假设先取 (i,j) 中靠左的三角形 (记作 L(i,j)), 哪些得先被吃掉是确定的.
先取 (i,j) 中靠右的 (R(i,j)) 同理.
DFS一下, 我们获得了 35 分, 时间复杂度 O(n^4).
观察, 发现 (i,j) 先取靠左的, (i,j-1) 也必然先取靠左的. 也就是说, L(i,j) 是在 L(i,j-1) 的基础上得到的. 同理, R(i,j) 是在 R(i,j+1) 的基础上得到的. 那么, 先枚举行, 再枚举列, vis 数组改为每行清空一遍, 就可以获得满分了, 时间复杂度 O(n^3).
如果 (i,j) 在求解 L(i,j-1) 时已经被吃掉, 则无解; 如果依赖关系成环, 则无解.