扫描线优化DP + 单调队列优化DP

扫描线优化 \(DP\)

扫描线的功能其实就是可以二维数点。

例题：P3431 [POI 2005] AUT-The Bus

这道题其实有两种做法，一种是树状数组维护\(x\)或\(y\)，另一种是cdq分治。

1. 树状数组

这种方法是最简单的，因为我们按照\(x\)或\(y\)排序之后，就可以用树状数组来维护另一维即可。

代码：

戳我喵~

#define lowbit(x) x & (-x)

int n, m, k, M;
array<int, 3> a[N], b[N];
int tree[N];
int Y[N];

void update(int x, int add) {
	for (; x <= M; x += lowbit(x)) tree[x] = max(tree[x], add);
}

int query(int x) {
	int ans = 0;
	for (; x; x -= lowbit(x)) ans = max(ans, tree[x]);
	return ans;
}

signed main() {
	n = re, m = re, k = re;
	for (int i = 1; i <= k; i++) a[i][0] = re, a[i][1] = re, a[i][2] = re, Y[i] = a[i][1];
	sort(Y + 1, Y + 1 + k);//需要离散化！
	M = unique(Y + 1, Y + 1 + k) - Y - 1;
	for (int i = 1; i <= k; i++) a[i][1] = lower_bound(Y + 1, Y + 1 + M, a[i][1]) - Y;
	sort(a + 1, a + 1 + k);
	for (int i = 1; i <= k; i++) {
		int cnt = query(a[i][1]) + a[i][2];
		update(a[i][1], cnt);
	}
	wr(query(M)), endl;
}

2. cdq分治

知周所众，cdq分治可以解决偏序问题，那么这道题就是一个二维偏序+DP模版。

详情见这里。

单调队列优化DP

使用范围

当 DP 状态转移方程式长得像下面式子的都可以用单调队列优化 DP

\[dp_i = \max_{L_i \le j \le R_i}(dp_j + F(i) + G(j)) \]

因为 \(F(i)\) 对于在枚举的 \(j\) 中，他就是一个定值，所以可以分离出来，那么式子就变成了：

\[dp_i = F(i) + \max_{L_i \le j \le R_i}(dp_j + G(j)) \]

所以用滑动窗口就能维护了。

例题：P1714 切蛋糕

设 \(dp_i\) 表示以 \(i\) 结尾的最大子段和， \(sum_i\) 表示前缀和。

那么方程为：

\[dp_i = \max_{i - M \le j \le i - 1}(sum_i - sum_j) \]

那么分离定值，就变成了：

\[dp_i = sum_i + \max_{i - M \le j \le i - 1}(-sum_j) \]

那么就是维护 \(\min_{i - M \le j \le i - 1}(sum_j)\)

那么就简单了。

戳我喵~

int cnt[N];

signed main() {
	int n = re, m = re;
	for (int i = 1; i <= n; i++) cnt[i] = cnt[i - 1] + re;
	deque<int> q;
	q.push_back(0);
	int ans = -1e9;
	for (int i = 1; i <= n; i++) {
		while(!q.empty() && q.front() + m < i) q.pop_front();
		while (!q.empty() && cnt[q.back()] >= cnt[i]) q.pop_back();
		q.push_back(i);
		if (q.front() != i) ans = max(ans, cnt[i] - cnt[q.front()]);
		else ans = max(ans, cnt[i] - cnt[i - 1]); //特判，有可能全是负的，但是必须选
	}
	wr(ans), endl;
}