Solution to「NOI2005」瑰丽华尔兹。
单调队列优化 DP。
不难发现，题意可转化为：
从 \((x,y)\) 出发，按顺序向 \(d_i\) 方向移动 \([0,ti−si+1]\) 距离，问最大移动距离。
为了方便描述，我们把一次「向 \(d_i\) 方向移动 \([0,ti−si+1]\) 距离」的操作称为「一步」。
设计状态。不难发现位置信息必须出现在 DP 的维度中（因为当前位置会影响下一步滑动的距离），而其他信息均不会对下一步滑动产生影响。
故可令 \(fi,j\) 表示完成当前次滑动后，从起点滑动到 \((i,j)\) 可得到的最大滑动距离。
以方向上为例，可列 DP 式：
\[ f_{i,j}=\max_{i<k≤i+(ti−si+1)}\{f_{k,j}+k−i\} \]
此时可枚举每一列的所有状态，使用单调队列优化。
但实际操作中会出现问题。因为单调队列从下向上更新状态时，\(f_{k,j}\) 会比 \(f_{i,j}\) 先更新（参考 01 背包倒序枚举容量），导致每一「步」会重复被走很多次。但单调队列的特性限制了我们只能从下向上枚举，此时可新开一个数组记录 \(f\) 当次被更新之前的值。
障碍物如何处理呢？我们知道，如果 \((i,j)\) 下面某一位置有障碍物，那么障碍物下面所有的 \((k,j)\) 都不能用于更新 \(f_{i,j}\)（因为被挡住了滑不上来）。所以我们在从下往上枚举时，遇到障碍物就清空单调队列即可。
下、左、右方向的处理方式类似。
只需顺序执行操作，根据当前操作方向对应处理即可。
namespace XSC062 {
using namespace fastIO;
const int maxn = 205;
const int inf = 1e18;
int q[maxn];
char a[maxn][maxn];
int f[maxn][maxn], d[maxn][maxn];
int n, m, x, y, k, u, h, t, res;
inline int max(int x, int y) {
return x > y ? x : y;
}
int main() {
memset(f, -0x3f, sizeof (f));
read(n), read(m);
read(x), read(y), read(k);
f[x][y] = 0;
for (int i = 1; i <= n; ++i)
scanf("%s", a[i] + 1);
while (k--) {
read(x), read(y), read(u);
y = y - x + 1;
if (u == 1) {
for (int j = 1; j <= m; ++j) {
h = 1, t = 0;
for (int i = n; i; --i) {
if (a[i][j] == 'x') {
h = 1, t = 0;
continue;
}
while (h <= t && q[h] - i > y)
++h;
d[i][j] = f[i][j];
if (h <= t) {
f[i][j] = max(f[i][j],
d[q[h]][j] + q[h] - i);
}
while (h <= t && d[i][j] + i
>= d[q[t]][j] + q[t])
--t;
q[++t] = i;
}
}
}
else if (u == 2) {
for (int j = 1; j <= m; ++j) {
h = 1, t = 0;
for (int i = 1; i <= n; ++i) {
if (a[i][j] == 'x') {
h = 1, t = 0;
continue;
}
while (h <= t && i - q[h] > y)
++h;
d[i][j] = f[i][j];
if (h <= t) {
f[i][j] = max(f[i][j],
d[q[h]][j] + i - q[h]);
}
while (h <= t && d[i][j] - i
>= d[q[t]][j] - q[t])
--t;
q[++t] = i;
}
}
}
else if (u == 3) {
for (int i = 1; i <= n; ++i) {
h = 1, t = 0;
for (int j = m; j; --j) {
if (a[i][j] == 'x') {
h = 1, t = 0;
continue;
}
while (h <= t && q[h] - j > y)
++h;
d[i][j] = f[i][j];
if (h <= t) {
f[i][j] = max(f[i][j],
d[i][q[h]] + q[h] - j);
}
while (h <= t && d[i][j] + j
>= d[i][q[t]] + q[t])
--t;
q[++t] = j;
}
}
}
else {
for (int i = 1; i <= n; ++i) {
h = 1, t = 0;
for (int j = 1; j <= m; ++j) {
if (a[i][j] == 'x') {
h = 1, t = 0;
continue;
}
while (h <= t && j - q[h] > y)
++h;
d[i][j] = f[i][j];
if (h <= t) {
f[i][j] = max(f[i][j],
d[i][q[h]] + j - q[h]);
}
while (h <= t && d[i][j] - j
>= d[i][q[t]] - q[t])
--t;
q[++t] = j;
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
res = max(res, f[i][j]);
}
}
print(res);
return 0;
}
} // namespace XSC062