[NOI 2005] 瑰丽华尔兹：dp+单调队列

本文主要是介绍[NOI 2005] 瑰丽华尔兹：dp+单调队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

状态转移方程，以船体向南倾斜为例，其中 $f[i][j][k]$ 表示经历前k个时间段后停留在第i行第j列的最长滑行距离：

f [i] [j] [k] = m a x {f [i - d] [j] [k - 1] + d, 0 \leq d < 离 前 面 最 近 的 障 碍 物 的 距 离}

$f[i][j][k] = max\{f[i-d][j][k-1]+d, 0 \le d \lt 离前面最近的障碍物的距离\}$
注意到需要考虑的状态是同一列上的一段区间，我想到用线段树优化转移。每行每列各两棵，维护

f[i][j][k]+i $f[i][j][k]+i$ 等，时间复杂度

O(n2k lgn) $O(n^2k\ lg n)$ ，还有大O记号下隐藏的常数。
具有可行性，但是能否做得更好呢？
贺神说它要用单调队列，我咋没用上呢？
确定递推顺序的时候，发现查询的区间有许多重叠，就像——滑动窗口。再者，同样以南为例，按照i递增的顺序递推，如果

f [i'] [j] [k] + i' \geq f [i] [j] [k] + i a n d i' > i

$f[i'][j][k]+i' \ge f[i][j][k]+i \ and\ i' \gt i$
那么

f[i′][j][k] $f[i'][j][k]$ 不会差于

f[i][j][k] $f[i][j][k]$ ，后者可以不再考虑。

开始写代码吧。东南西北四种对称情形，抽取它们的内在结构，避免冗长的代码——这一点黄学长做得比我好。截至目前（2016年9月10日晚），我的程序是bzoj上倒数第三慢的，推测主要原因来自于三维数组寻址。

昨天晚上写好了，但是有bug——某处f[i][j][k-1]误作f[i][j][k]。用当年的数据，也就30分了。我本应该发现——之前因为另一个问题输出中间变量，和我预期的不一样。但是由于答案正确，没有深究。注意细节。关注每一处异常。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
using namespace std;
const int MAX_N = 200, MAX_M = 200, MAX_K = 200+1, INF = 1<<30;
int N, M, head, tail, f[MAX_N][MAX_M][MAX_K];
char m[MAX_N][MAX_M];
struct Point {int i, j;int operator-(const Point& rhs) const{return abs(i - rhs.i + j - rhs.j);}int get_f(int k){return f[i][j][k];}
} q[MAX_N];void upd(int i, int j, int k, int t)
{if (m[i][j] == 'x') {tail = head;return;}Point p = (Point){i, j};while (head != tail && q[head] - p > t)++head;while (head != tail && q[tail-1].get_f(k-1) + (q[tail-1] - p) <= f[i][j][k-1])--tail;q[tail++] = p;f[i][j][k] = q[head].get_f(k-1) + (q[head] - p);    
}inline void north(int k, int t)
{for (int j = 0; j < M; ++j) {head = tail = 0;for (int i = N-1; i >= 0; --i)upd(i, j, k, t);}
}inline void south(int k, int t)
{for (int j = 0; j < M; ++j) {head = tail = 0;for (int i = 0; i < N; ++i)upd(i, j, k, t);}
}inline void east(int k, int t)
{for (int i = 0; i < N; ++i) {head = tail = 0;for (int j = 0; j < M; ++j)upd(i, j, k, t);}
}inline void west(int k, int t)
{for (int i = 0; i < N; ++i) {head = tail = 0;for (int j = M-1; j >= 0; --j)upd(i, j, k, t);}
}template<typename T>
void read(T& x)
{x = 0;char c = getchar();while (!isdigit(c))c = getchar();while (isdigit(c)) {x = x*10 + c - '0';c = getchar();}
}int main()
{int x, y, K;read(N); read(M); read(x); read(y); read(K);for (int i = 0; i < N; ++i)for (int j = 0; j < M; ++j)f[i][j][0] = -INF;f[x-1][y-1][0] = 0;for (int i = 0; i < N; ++i)scanf("%s", m[i]);int s, t, d, tm;for (int i = 1; i <= K; ++i) {read(s); read(t); read(d);tm = t-s+1;switch (d) {case 1:north(i, tm); break;case 2:south(i, tm); break;case 3:west(i, tm); break;case 4:east(i, tm); break;}}int ans = -INF;for (int i = 0; i < N; ++i)for (int j = 0; j < M; ++j)ans = max(ans, f[i][j][K]);printf("%d\n", ans);return 0;
}