LOJ 2604 「NOIP2012」开车旅行

题目链接

之前听学长讲过，好像是在 dp 专题讲的？
这东西好像不是很 dp 啊。
先想想暴力的做法。
问题一直接枚举起点后模拟一下，\(\mathjaxcal{O}(n^3)\)
问题二一样的模拟...

有两个优化，可以先预处理一下每个点对应的最小和次小的目的地，之后直接走。
二是每次决策好像都差不多，可不可以一次多走几步...

第一个，因为只能往东走，所以西边的点对东方没有影响。
可以在一个 set 里面按顺序进行查询，每次查完就删除现在的点, \(\mathjaxcal{O}(n\log n)\)
第二个，可以倍增处理。
\(fi][j]\)表示从\(i\)开始走\(2^j\)步到的点是谁。
每一步的定义是\(A,B\)各开了一次车。 \(A[i][j]\)表示从\(i\)开始\(2^j\)步，\(A\)驾驶的总距离。
\(B[i][j]\)同理。

注意判断一下走不动的情况，即\(f\)为\(0\)，和最后\(A\)是否可以单独走一步。
时间复杂度\(\mathjaxcal{O}(n\log n)\)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5 + 5;
int n, m, h[N], d1[N], d2[N], f[N][19];
ll A[N][19], B[N][19], s1, s2, x0;

struct cmp {
	bool operator () (int x, int y) {
		return h[x] < h[y];
	}
};
set<int, cmp> s;
set<int>::iterator it, t;

int dis(int i, int j) {
	return abs(h[i] - h[j]);
}
void check(int i, int j) {
	if (!d1[i]) {
		d1[i] = j;
		return;
	}
    if (dis(i, j) < dis(i, d1[i]) || (dis(i, j) == dis(i, d1[i]) && h[j] < h[d1[i]])) {
		d2[i] = d1[i], d1[i] = j;
	} else if (!d2[i] || dis(i, j) < dis(i, d2[i]) || (dis(i, j) == dis(i, d2[i]) && h[j] < h[d2[i]])) d2[i] = j;
}

void solve(int p, ll x) {
    s1 = s2 = 0;
	for (int j = 16; j + 1; j--) {
		if (f[p][j] && s1 + s2 + A[p][j] + B[p][j] <= x) {
			s1 += A[p][j];
			s2 += B[p][j];
			p = f[p][j];
		}
	}
	if (d2[p] && s1 + s2 + A[p][0] <= x) s1 += A[p][0];
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]), s.insert(i);
	scanf("%lld", &x0);
	for (int i = 1; i <= n; i++) {
        it = s.lower-bound(i);
        if (it != s.begin()) {
			t = it;
			check(i, *--t);
			if (t != s.begin()) check(i, *--t);
		}
		if (++it != s.end()) {
			check(i, *it);
			if (++it != s.end()) check(i, *it);
		}
		s.erase(i);
	}
	for (int i = 1; i <= n; i++) f[i][0] = d1[d2[i]], A[i][0] = dis(i, d2[i]), B[i][0] = dis(d2[i], d1[d2[i]]);
	for (int j = 0; j < 16; j++)
		for (int i = 1; i <= n; i++) {
            f[i][j + 1] = f[f[i][j]][j];
			A[i][j + 1] = A[f[i][j]][j] + A[i][j];
			B[i][j + 1] = B[f[i][j]][j] + B[i][j];
		}
	ll a = 1e9, b = 0;
	int pos = 0;
	scanf("%d", &m);
	for (int i = 1; i <= n; i++) {
        solve(i, x0);
		if (!s2) {
            if (!b) {
				if (h[i] > h[pos]) pos = i;
			}
		} else {
			if (s2 * a > s1 * b || (s2 * a == s1 * b && h[i] > h[pos])) {
                a = s1, b = s2, pos = i;
			}
		}
	}
	printf("%d\n", pos);
	for (int i = 1; i <= m; i++) {
	    int S; ll x;
		scanf("%d %lld", &S, &x);
		solve(S, x);
		printf("%lld %lld\n", s1, s2);
	}
	return 0;
}