P2254 [NOI2005] 瑰丽华尔兹

//单调队列优化DP经典题
#include<bits/stdc++.h>
using namespace std;
int n, m, X, Y, K;
bool mp[1001][1001];
int f[201][201][201], qx[1001], qy[1001], ans = -114514;
int dx[5] = {0, -1, 1, 0, 0}, dy[5] = {0, 0, 0, -1, 1};
struct st {
    int t, d;
}a[100101];
int dist(int x, int y, int a, int b) { return abs(x - a) + abs(y - b); }
void solve(int cx, int cy, int k) {
    int fl = 0, re = 0;
    while  (1) {
        if (cx > n || cx < 1 || cy > m || cy < 1) break;
        //超出范围直接break掉 
        while (fl < re && dist(cx, cy, qx[fl], qy[fl]) > a[k].t) fl ++;
        //当前队头的距离(就是我要移动花的时间)，大于了我这一段最长能移动的时间，那我就把它从队尾里扔掉 
        while (fl < re && !mp[cx][cy]) re --;
        //这个格子无法走的话我就把它从队头里扔掉 
        while (fl < re && f[k - 1][qx[re - 1]][qy[re - 1]] + dist(qx[re - 1], qy[re - 1], cx, cy) < f[k - 1][cx][cy]) re --;
        //上一个状态的最长距离 + 转移的距离 小于目标节点的距离，无法得到更优状态，直接丢出队头=.= 
        if (mp[cx][cy]) qx[re] = cx, qy[re ++] = cy, f[k][cx][cy] = f[k - 1][qx[fl]][qy[fl]] + dist(qx[fl], qy[fl], cx, cy);
        //如果当前这个格子可以走 (满足单调性易证)，把这个格子放到队列里面, 转移状态 
        cx += dx[a[k].d], cy += dy[a[k].d];
        //按照当前方向再走一步 
    }
}
int main() {
    cin >> n >> m >> X >> Y >> K;
    memset(f, -0x3f3f3f3f, sizeof(f));
    f[0][X][Y] = 0;
    //设定初始状态 
    for (int i = 1; i <= n; i ++) {
        string s;
        cin >> s;
        for (int j = 0; j < s.size(); j ++)
            mp[i][j + 1] =  (s[j] == '.');
    }
    for (int i = 1, l, r; i <= K; i ++) {
        scanf("%d %d %d", &l, &r, &a[i].d);
        a[i].t = r - l + 1;
        //把耗的时间存起来 
    }
    for (int i = 1; i <= K; i ++) {
        if (a[i].d == 1) for (int j = 1; j <= m; j ++) solve(n, j, i);
        else if (a[i].d == 2) for (int j = 1; j <= m; j ++) solve(1, j, i);
        else if (a[i].d == 3) for (int j = 1; j <= n; j ++) solve(j, m, i);
        else for (int j = 1; j <= n; j ++) solve(j, 1, i);
    }
    //四个方向都搞一个单调队列，分别转移出最优答案 
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            ans = max(ans, f[K][i][j]);
    cout << ans;
    return 0;
}