Let bygones be bygones

Let bygones be bygones.

Oh, I have.

欢乐 dp 场。总之我们通过神秘方法，一个像样的正解都没有写，获得了三位数的好成绩。

六出祁山

一个有脑子就会写的暴力 dp，定义 \(f_{i, j}\) 表示处理到第 \(i\) 个，高度改为 \(j\)。有 \(f_{i, j} = f_{i - 1, k} + | h_i - j| (|k - j| \leq d)\)。然后这样是 \(O(n d^ 2)\) 的，考虑优化。那么显然只能优化这个状态数，其它的目前还优化不了。然后就有一个非常离谱的优化，感性理解一下，相邻差都不大于 \(d\)，还在 \(h\) 元素的基础上修改，那么是不是最优状态可以是 \(h_i + kd, k \in \mathbb{Z}\) 呢？

然后状态数从 \(d\) 变到了 \(n ^ 2\)。时间复杂度 \(O(n ^ 5)\)。重新看原来的 dp 柿子，\(j\) 固定，\(k\) 显然也固定，那么 \(j\) 每次循环都增加，只需要用滑动窗口维护 \(k\) 就好了。时间复杂度 \(O(n ^ 3)\)。甚至可以 set。

namespace liuzimingc {
const int N = 305, M = 9e4 + 5, INF = 1e9;
#define endl '\n'
#define int long long

int n, d, h[N], v, a[N], ans, q[M];
int f[N][M];
vector<int> lsh;

int get(int x) {
	return lower_bound(lsh.begin(), lsh.end(), x) - lsh.begin();
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> d;
	for (int i = 1; i <= n; i++) cin >> h[i], v = max(v, h[i]);
	if (abs(h[1] - h[n]) > (n - 1) * d) return cout << -1 << endl, 0;
	for (int i = 1; i <= n; i++)
		for (int j = -n; j <= n; j++) {
			int x = h[i] + j * d;
			if (x >= 0 && x <= v) lsh.push_back(x);
		}
	sort(lsh.begin(), lsh.end());
	lsh.resize(unique(lsh.begin(), lsh.end()) - lsh.begin());
	memset(f, 0x3f, sizeof(f));
	f[1][get(h[1])] = 0;
	for (int i = 2; i <= n; i++) {
		int head = 1, tail = 0, r = 0;
		for (int j = 0; j < lsh.size(); j++) {
			while (head <= tail && lsh[q[head]] < lsh[j] - d) head++;
			while (r < lsh.size() && lsh[r] <= lsh[j] + d) {
				while (head <= tail && f[i - 1][q[tail]] > f[i - 1][r]) tail--;
				q[++tail] = r++;
			}
			f[i][j] = f[i - 1][q[head]] + abs(lsh[j] - h[i]);
		}
	}
	cout << f[n][get(h[n])] << endl;
	return 0;
}
#undef int
} // namespace liuzimingc

水淹七军

糊里糊涂，总之用了一个完全不知道的 Mirsky（Dilworth）定理：\(S\) 的最长链长度等于最小的反链覆盖数。

然后转换成这个，然后就开始分层 dp 了。是的我是 C 的，现在都没懂，我骄傲