原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最大值

1.2 题目背景、允许、禁止与限制

背景：有一个 $n\times m$ 的家具网格，其中.代表无家具，x表示有家具；另给定 $K$ 个时间区间 $[s_i,t_i]$，代表该时间内倾斜方向。还有一个钢琴，初始位置为 $(x,y)$
允许：对于每个时刻有两种选择

• 固定钢琴，使其位置不变
• 不固定钢琴，使其按照该时间点所属时间段倾斜方向移动 $1$ 格

求钢琴最远滑行距离
限制：对于任意时刻钢琴均不应出现在x的位置上

1.3 题目数据范围与猜测

$1 \le n,m \le 200,K\le200,T\le40000 \longrightarrow O(Knm)$

1.4 一句话概括题意

有一个网格，其中有可以到达的点，也有始终不能到达的点。在每个时刻有两种选择，最终使得某物从 $(x,y)$ 开始移动距离最长

2 题目破题推导

显然这题要用 $\huge{dp}$

2.1 第一步：正向思维转逆向思维

先尝试按“每秒”进行dp：$dp[t][x][y]$
发现时间 $t$ 太大（$\le40000$），会MLE和TLE
那转换思维
发现 $K\le200$，远远小于时间点
那么我们不按“每秒”推，按“时间段”推

2.2 第二步：分情况讨论

第 $k$ 个时间段在 $(i,j)$，必然是从第 $k-1$ 个时间段从 $(i2,j2)$ 沿其给定方向滑动来的
而因为一个时间段内只能朝一个方向滑，所以 $(i,j)$ 和 $(i2,j2)$ 必定在同一行或同一列，且距离不超过时间段长度 $len=t_i-s_i+1$
所以按四个方向分别讨论

2.3 第三步：数学·分离变量（单调队列实现）

举个例子，对于向上（北）倾斜
step1:
观察转移方程：$dp[k][i][j] = dp[k - 1][i2][j] + (i2 - i)$
发现起点里的价值dp和距离 $(i2-i)$ 混在一起，无法直接比较候选上一个点

• 比如只考虑 $dp[k-1][i2][j]$ 会漏掉一些本来更优的情况（简要概述：尽管到上一个点前移动的距离总和没那么远，但是由于上一个点离该点距离较远，所以累加起来反而这一个更优）
• 再比如考虑 $dp[k - 1][i2][j] + (i2 - i)$，那 $i$ 会变，会出现同一个起点在不同终点下得分不一样的情况，那么无法直接单调队列一个最值

step2:
那我们拆开距离的那一项，把 $(i2-i)$ 拆成 $i2-i$，将跟起点相关和跟终点相关的项分离开

step3:
接着重新组合式子
把式子改写为 $dp[k][i][j] = (dp[k - 1][i2][j] + i2) - i$
此时括号内只含起点信息，$-i$ 对所有候选起点都是固定常数

step4:
既然括号内只和起点有关，就可以将括号内的这一部分统一单调队列

step5:
得到最优起点后，减去终点 $i$
这个减去的 $i$ 就是：
把式子改写为 $dp[k][i][j] = (dp[k - 1][i2][j] + i2) - i$ 的时候这个外部的 $-i$

这就是数学分离思想在单调队列优化中的一种应用

3 模型匹配

上一部分已经讲述

4 最终代码（禁止抄袭，仅用于参考）

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

inline int read(){
    int num = 0;
    int f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-'){
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        num = (num << 3) + (num << 1) + (ch ^ 48);
        ch = getchar();
    }
    return num * f;
}
int n, m, x, y, K;
const int N = 222;
char mp[N][N];
int pre[N][N];
int cur[N][N];
struct time{
    int start, end;
    int dir;
}a[N];

int main(){

    n = read(), m = read(), x = read(), y = read(), K = read();
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            cin >> mp[i][j];
        }
    }
    for (int i = 1;i <= K;i++){
        a[i].start = read(), a[i].end = read(), a[i].dir = read();
    }
    memset(pre, -0x3f, sizeof(pre));
    pre[x][y] = 0;
    for (int k = 1;k <= K;k++){
        int len = a[k].end - a[k].start + 1;
        int dir = a[k].dir;
        memset(cur, -0x3f, sizeof(cur));
        if (dir == 1){
            for (int j = 1;j <= m;j++){
                deque<int> q;
                for (int i = n;i >= 1;i--){
                    if (mp[i][j] == 'x'){
                        q.clear();
                        continue;
                    }
                    int val = pre[i][j] + i;
                    while(!q.empty() && pre[q.back()][j] + q.back() < val){
                        q.pop_back();
                    }
                    q.push_back(i);
                    while(!q.empty() && q.front() - i > len){
                        q.pop_front();
                    }
                    if (!q.empty()){
                        cur[i][j] = max(cur[i][j], pre[q.front()][j] + q.front() - i);
                    }
                }
            }
        } else if (dir == 2) {
            for (int j = 1;j <= m;j++){
                deque<int> q;
                for (int i = 1;i <= n;i++){
                    if (mp[i][j] == 'x'){
                        q.clear();
                        continue;
                    }
                    int val = pre[i][j] - i;
                    while(!q.empty() && pre[q.back()][j] - q.back() < val){
                        q.pop_back();
                    }
                    q.push_back(i);
                    while(!q.empty() && i - q.front() > len){
                        q.pop_front();
                    }
                    if (!q.empty()){
                        cur[i][j] = max(cur[i][j], pre[q.front()][j] - q.front() + i);
                    }
                }
            }
        } else if (dir == 3){
            for (int i = 1;i <= n;i++){
                deque<int> q;
                for (int j = m;j >= 1;j--){
                    if (mp[i][j] == 'x'){
                        q.clear();
                        continue;
                    }
                    int val = pre[i][j] + j;
                    while(!q.empty() && pre[i][q.back()] + q.back() < val){
                        q.pop_back();
                    }
                    q.push_back(j);
                    while(!q.empty() && q.front() - j > len){
                        q.pop_front();
                    }
                    if (!q.empty()){
                        cur[i][j] = max(cur[i][j], pre[i][q.front()] + q.front() - j);
                    }
                }
            }
        } else {
            for (int i = 1;i <= n;i++){
                deque<int> q;
                for (int j = 1;j <= m;j++){
                    if (mp[i][j] == 'x'){
                        q.clear();
                        continue;
                    }
                    int val = pre[i][j] - j;
                    while(!q.empty() && pre[i][q.back()] - q.back() < val){
                        q.pop_back();
                    }
                    q.push_back(j);
                    while(!q.empty() && j - q.front() > len){
                        q.pop_front();
                    }
                    if (!q.empty()){
                        cur[i][j] = max(cur[i][j], pre[i][q.front()] - q.front() + j);
                    }
                }
            }
        }
        for (int i = 1;i <= n;i++){
            for (int j = 1;j <= m;j++){
                pre[i][j] = cur[i][j];
            }
        }
    }
    int ans = INT_MIN;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            ans = max(ans, cur[i][j]);
        }
    }
    printf("%d", ans);
    
    return 0;
}

错误点：经常会在线上评测OJ显示RE
不要忘记检查是不是for循环里的i,j写串了