原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：一个最大值
1.2 题目背景、允许、禁止与限制
背景：有一个 n×mn\times mn×m 的家具网格，其中.代表无家具，x表示有家具；另给定 KKK 个时间区间 [si,ti][s_i,t_i][si ,ti ]，代表该时间内倾斜方向。还有一个钢琴，初始位置为 (x,y)(x,y)(x,y)
允许：对于每个时刻有两种选择
* 固定钢琴，使其位置不变
* 不固定钢琴，使其按照该时间点所属时间段倾斜方向移动 111 格
求钢琴最远滑行距离
限制：对于任意时刻钢琴均不应出现在x的位置上
1.3 题目数据范围与猜测
1≤n,m≤200,K≤200,T≤40000⟶O(Knm)1 \le n,m \le 200,K\le200,T\le40000 \longrightarrow O(Knm)1≤n,m≤200,K≤200,T≤40000⟶O(Knm)
1.4 一句话概括题意
有一个网格，其中有可以到达的点，也有始终不能到达的点。在每个时刻有两种选择，最终使得某物从 (x,y)(x,y)(x,y) 开始移动距离最长
2 题目破题推导
显然这题要用 dp\huge{dp}dp
2.1 第一步：正向思维转逆向思维
先尝试按“每秒”进行dp：dp[t][x][y]dp[t][x][y]dp[t][x][y]
发现时间 ttt 太大（≤40000\le40000≤40000），会MLE和TLE
那转换思维
发现 K≤200K\le200K≤200，远远小于时间点
那么我们不按“每秒”推，按“时间段”推
2.2 第二步：分情况讨论
第 kkk 个时间段在 (i,j)(i,j)(i,j)，必然是从第 k−1k-1k−1 个时间段从 (i2,j2)(i2,j2)(i2,j2) 沿其给定方向滑动来的
而因为一个时间段内只能朝一个方向滑，所以 (i,j)(i,j)(i,j) 和 (i2,j2)(i2,j2)(i2,j2) 必定在同一行或同一列，且距离不超过时间段长度 len=ti−si+1len=t_i-s_i+1len=ti −si +1
所以按四个方向分别讨论
2.3 第三步：数学·分离变量（单调队列实现）
举个例子，对于向上（北）倾斜
step1:
观察转移方程：dp[k][i][j]=dp[k−1][i2][j]+(i2−i)dp[k][i][j] = dp[k - 1][i2][j] + (i2 - i)dp[k][i][j]=dp[k−1][i2][j]+(i2−i)
发现起点里的价值dp和距离 (i2−i)(i2-i)(i2−i) 混在一起，无法直接比较候选上一个点
* 比如只考虑 dp[k−1][i2][j]dp[k-1][i2][j]dp[k−1][i2][j] 会漏掉一些本来更优的情况（简要概述：尽管到上一个点前移动的距离总和没那么远，但是由于上一个点离该点距离较远，所以累加起来反而这一个更优）
* 再比如考虑 dp[k−1][i2][j]+(i2−i)dp[k - 1][i2][j] + (i2 - i)dp[k−1][i2][j]+(i2−i)，那 iii 会变，会出现同一个起点在不同终点下得分不一样的情况，那么无法直接单调队列一个最值
step2:
那我们拆开距离的那一项，把 (i2−i)(i2-i)(i2−i) 拆成 i2−ii2-ii2−i，将跟起点相关和跟终点相关的项分离开
step3:
接着重新组合式子
把式子改写为 dp[k][i][j]=(dp[k−1][i2][j]+i2)−idp[k][i][j] = (dp[k - 1][i2][j] + i2) - idp[k][i][j]=(dp[k−1][i2][j]+i2)−i
此时括号内只含起点信息，−i-i−i 对所有候选起点都是固定常数
step4:
既然括号内只和起点有关，就可以将括号内的这一部分统一单调队列
step5:
得到最优起点后，减去终点 iii
这个减去的 iii 就是：
把式子改写为 dp[k][i][j]=(dp[k−1][i2][j]+i2)−idp[k][i][j] = (dp[k - 1][i2][j] + i2) - idp[k][i][j]=(dp[k−1][i2][j]+i2)−i 的时候这个外部的 −i-i−i
这就是数学分离思想在单调队列优化中的一种应用
3 模型匹配
上一部分已经讲述
4 最终代码（禁止抄袭，仅用于参考）
错误点：经常会在线上评测OJ显示RE
不要忘记检查是不是for循环里的i,j写串了
