P3431 [POI 2005] AUT-The Bus题解
sPERbEETLE
·
·
题解
题目大意
题目大意：
给定一个的 n \times m 格，其中有 k 个特殊点，每个特殊点包含 (x_i,y_i) 的权值 p_i。
只能向右或向上，求从 (1,1) 到 (n,m) 所能获得的最大权值和。
# 做法
我们看到了数据范围后，第一反应应该是离散化和从 $k$ 入手。
我们先想 DP 做法，我们设 $dp_i$ 表示到当前点 $i$ 能获得的最大权值和。
那么 DP 状态转移式为：
$$ dp_i = \max_{1 \le j \le i,x_j \le x_i,y_j \le y_i}(dp[j])+p_i$$
那么上述表达式中有一个条件是 $x_j \le x_i,y_j \le y_i$，看到这个，能联想到什么呢？二维偏序！
那么这道题的做法就出来了，cdq 分治和 DP。
先离散化 $y$，保证 cdq 分治中树状数组不会 MLE 和 RE。
我们先要按第一关键字 $x$ 来排序，如果相等就按 $y$ 来排序。
那么在 cdq 分治中，如果到了单一点，那么答案就是 $\max(p_l, dp_{id_l})$ 其中 $id_l$ 表示的是点 $l$ 的原始 $id$ 方便存答案，而取最大值就是因为有可能多次更改该点。
如果是一段区间，就要先处理左区间，再处理中间，最后处理左边，这是 cdq 分治内套 DP 的必须。
那么在处理中间的时候，我们不用像三维偏序一样再去排一次序，因为我们最开始排了一次序后，在 cdq 分治的过程中是一定有序的。
我们使用树状数组去维护 $y$ 坐标，如果 $x_i \le x_j$，就证明它一定保证了 $x$ 是合法的，每次更新答案时，我们需要查询不超过 $y_j$ 的合法点的最大权值，而树状数组的更新和查询也就是最大值的操作。
那么 DP 的转移就呼之欲出了。
$$ dp_{id_l} = \max(query(y_j)+p_j) $$
那么答案也就出来了。
代码：
```cpp
#include <bits/stdc++.h>
#define re read()
#define wr(n) write(n)
#define sp putchar(' ')
#define endl puts("")
const int N = 1e5 + 10, INF = 1e9;
const double ecnts = 1e-6;
using namespace std;
using lint = long long;
using ulint = unsigned long long;
using pii = pair<int, int>;
int read() { //快读
int f = 1, y = 0;
char c = getchar();
while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar();
while (isdigit(c)) y = (y << 3) + (y << 1) + (c ^ 48), c = getchar();
return y * f;
}
void write(int x) { //快写
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
int n, m, k;
struct node {
int x, y, p, id;
} a[N];
bool cmp(const node &X, const node &Y) {
return X.x == Y.x ? X.y < Y.y : X.x < Y.x;
} //排序规则
#define lowbit(x) x & (-x)
int tree[N];
void update(int x, int add) { //更新
for (; x <= k; 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;
}
int dp[N];
int Y[N];
void cdq(int l, int r) {
if (l == r) {
dp[a[l].id] = max(dp[a[l].id], a[l].p); //单点的权值
return ;
}
int mid = l + r >> 1;
cdq(l, mid); //枚举左区间
int i = l;
for (int j = mid + 1; j <= r; j++) { //处理中间
while (i <= mid && a[i].x <= a[j].x) update(a[i].y, dp[a[i].id]), i++; //加入x可行的点
dp[a[j].id] = max(query(a[j].y) + a[j].p, dp[a[j].id]); //更新DP
}
cdq(mid + 1, r); //枚举右区间
}
signed main() {
n = re, m = re, k = re;
for (int i = 1; i <= k; i++) a[i] = {re, re, re, i}, Y[i] = a[i].y;
sort(Y + 1, Y + 1 + k); //离散化
int M = unique(Y + 1, Y + 1 + k) - Y - 1;
for (int i = 1; i <= k; i++) a[i].y = lower_bound(Y + 1, Y + 1 + M, a[i].y) - Y;
sort(a + 1, a + 1 + k, cmp);
cdq(1, k);
int ans = 0;
for (int i = 1; i <= k; i++) ans = max(ans, dp[i]); //最后答案的统计
wr(ans), endl;
}
```