「NOI 2005」瑰丽华尔兹

题目大意：给定一个 $n \times m$ 的棋盘，起点为 $(x,y)$，给定 $k$ 个时间段，每个时间段给出一个移动的方向，每次可以往当前指定的方向移动一步或停在原地，不能撞到障碍物或走出棋盘，问最多能走多少步。$n,m,k \leq 200$

设 $f[k][i][j]$ 表示第 $k$ 个时间段结束时走到 $(i,j)$ 的最长滑动距离,无法到达表示为 $−\infty$，设 $len=t_k−s_k+1$，即第 $k$ 个时间段的持续时间。

以向右走为例，有状态转移方程

$$f[k][i][j]=\max\limits_{j−len≤t≤j}(f[k−1][i][t]+j−t)=\max\limits_{j−len≤t≤j}(f[k−1][i][t]−t)+j$$

单调队列维护 $t$ 单调递增，$f$ 单调递减。

#include <cstdio>

const int N = 205, INF = 0x7fffffff;
const int dx[5] = {0, -1, 1, 0, 0};
const int dy[5] = {0, 0, 0, -1, 1};

char a[N][N]; int n, m, f[N][N], q[N][2], ans;

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
int max(int x, int y) {
    return x > y ? x : y;
}
void solve(int x, int y, int len, int d) {
    int head = 1, tail = 0;
    for (int i = 1; x >= 1 && x <= n && y >= 1 && y <= m; x += dx[d], y += dy[d], ++i) {
        if (a[x][y] == 'x') head = 1, tail = 0;
        else {
            while (head <= tail && q[tail][1] + i - q[tail][0] < f[x][y]) --tail;
            q[++tail][0] = i, q[tail][1] = f[x][y];
            if (q[tail][0] - q[head][0] > len) ++head;
            f[x][y] = q[head][1] + i - q[head][0];
            ans = max(ans, f[x][y]);
        }
    }
}

int main() {
    n = read(), m = read(); int x = read(), y = read(), k = read();
    for (int i = 1; i <= n; ++i) scanf("%s", a[i] + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) f[i][j] = -INF;
    f[x][y] = 0;
    while (k--) {
        int s = read(), t = read(), d = read();
        if (d == 1) for (int i = 1; i <= m; ++i) solve(n, i, t - s + 1, d); //up
        if (d == 2) for (int i = 1; i <= m; ++i) solve(1, i, t - s + 1, d); //down
        if (d == 3) for (int i = 1; i <= n; ++i) solve(i, m, t - s + 1, d); //left
        if (d == 4) for (int i = 1; i <= n; ++i) solve(i, 1, t - s + 1, d); //right
    }
    printf("%d\n", ans);
    return 0;
}

时间复杂度 $O(nmk)$