单调队列优化DP（补）

前言：

DP显然是OI中的一个重要且高频的考点，然而友善的出题人大多不会只考一个推转移方程，往往需要结合一些优化。

单调队列：

看这个的应该都会，不写了，扔个板子上去。

P1886 滑动窗口 /【模板】单调队列

优化DP：

显然，并不是所有的DP都可以用单调队列优化。一般来说，仅有形如

\[dp_{i} = \min/\max_{j = l_{i}}^{i - 1} \left \{ f_{j} \right \} + x \]

且满足 \(l_{i} ≤ l_{i + 1}\) 的DP才能优化。

翻译成人话：对于序列中的每一个点，从其左侧的一段决策区间内的最值进行转移，并且决策区间随着序列区间随着序列下标的增大不断右移。（其实就是一遍滑动窗口）

还是上边的式子，设 \(j <k\)，若 \(d_{j}\) 劣于 \(f_{k}\) 的话，那么决策区间移动到 \(k\) 以后，\(j\) 以后永远不会成为最优决策点。

所以维护一个双端队列，满足下标递增，决策性递减。队首即为最优决策点。当队首超出了区间范围，直接出队。同时为了保证单调性，从队尾新加入点前，把队列中比它劣的点从队尾依次出队。

一些例题：

P2254 [NOI2005] 瑰丽华尔兹

给定一个 \(n \times m\) 的矩阵，以 \((x,y)\) 为起点，一共 \(k\) 段时间，每段时间为 \(\left [ s_{i}，t_{i} \right ]\)，每秒可以向 \(d_{i}\) 方向运动一个单位或不动，且不能超出矩阵，不能走到给出的矩阵的障碍物处，求运动的最长距离。

首先考虑暴力DP，设 \(dp[t][i][j]\) 代表在时刻 \(t\)，运动到了 \((i,j)\) 的最长距离，不难得到转移方程为：

\[dp[t][i][j] = max(dp[t][i][j], dp[t - 1][i - dx_{d}][j - dy_{d}] + 1) \]

其中 \(d\) 代表方向，\(dx_{d}\) 代表移动时横坐标的变化量，\(dy_{d}\) 代表移动时纵坐标的变化量。然而它的时空复杂度都高达 \(O(n \times m \times t)\)。

考虑优化，每个时间段只能向一个方向移动，所以按照时间段进行DP。设 \(dp[k][i][j]\) 代表在第 \(k\) 段时间，运动到 \((i,j)\) 的最长距离。

转移方程有:

\[dp[k][i][j] = \max{dp[k - 1][i'][j']} + dis(i,j,i',j') \]

\(i'，j'\) 表示上一个合法的位置。并且 \((i,j)\) 和 \((i',j')\) 一定在同一行或者同一列上。

考虑到方程中要求 \(\max\)，且求可能拓展的状态有线性关系，所以考虑单调队列。

按照读入的每个时间段的方向，枚举每个方向的起始点。在单调队列里记录所在列或行某一个节点减去它到这一列或行初始位置的距离。对于每个点，用步数（就是初始点到当前点的距离）加上队首。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int MAXN = 210, MAXT = 40010;
const int dx[5] = {0, -1, 1, 0, 0};
const int dy[5] = {0, 0, 0, -1, 1};
int n, m, x, y, k, ans;
char hall[MAXN][MAXN];
int dp[MAXN][MAXN];

struct Ship{
    int st, ed, opt;
}sh[MAXT];

struct Line{
    int x, y, val;
}q[MAXT];

int head = 1, tail = 0;

inline int Get_dis(int ax, int ay, int bx, int by){
    return abs(ax - bx) + abs(ay - by);
}

void Modify(int x, int y, int opt, int len){
    head = 1, tail = 0;

    while(x >= 1 && x <= n && y >= 1 && y <= m){
        if(hall[x][y] == 'x') //撞到家具了，之前搞的作废 
            head = 1, tail = 0;
        else{
            while(head <= tail && q[tail].val + Get_dis(x, y, q[tail].x, q[tail].y) < dp[x][y])
                tail--; //对答案肯定没有贡献，出去 
            q[++tail] = ((Line){x, y, dp[x][y]});
            while(head <= tail &&  max(abs(x - q[head].x), abs(y - q[head].y)) > len)
                head++;
            dp[x][y] = max(dp[x][y], q[head].val + Get_dis(x, y, q[head].x, q[head].y));
            ans = max(ans, dp[x][y]);
        }

        x += dx[opt];
        y += dy[opt];
    }
}

inline int read(){
    int x = 0, f = 1;
    char c = getchar();

    while(c < '0' || c > '9'){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }

    return x * f;
}

int main(){
    n = read(), m = read(), x = read(), y = read(), k = read();
    for(register int i = 1; i <= n; i++)
        scanf("%s", hall[i] + 1);
    memset(dp, -0x3f, sizeof(dp));
    dp[x][y] = 0;
    for(register int i = 1; i <= k; i++){
        sh[i].st = read(), sh[i].ed = read(), sh[i].opt = read();
        int len = sh[i].ed - sh[i].st + 1;
        if(sh[i].opt == 1)
            for(register int j = 1; j <= m; j++)
                Modify(n, j, sh[i].opt, len);
        else if(sh[i].opt == 2)
            for(register int j = 1; j <= m; j++)
                Modify(1, j, sh[i].opt, len);
        else if(sh[i].opt == 3)
            for(register int j = 1; j <= n; j++)
                Modify(j, m, sh[i].opt, len);
        else if(sh[i].opt == 4)
            for(register int j = 1; j <= n; j++)
                Modify(j, 1, sh[i].opt, len);
    }

    printf("%d", ans);

    return 0;
}