扫描线优化 \(DP\)
扫描线的功能其实就是可以二维数点。
例题：P3431 [POI 2005] AUT-The Bus
这道题其实有两种做法，一种是树状数组维护\(x\)或\(y\)，另一种是cdq分治。
- 树状数组
这种方法是最简单的，因为我们按照\(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;
}
- 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;
}