题目链接:POI2005-AUT-The Bus
题意:
一个街区,有n条南北干道,m条东西干道,一辆公交从左下角出发,只能向北或者向东开,每个十字路口有一定的人数,问最多能接到多少乘客。
题解:
二维偏序问题。
先把第二维离散化,然后以第一维排序,第二维用树状数组维护,每个点队答案的贡献为$max(val[1],val[2],···,val[a[i].y])+a[i].v$,然后该点队后面点的影响$val[i]=max(val[i],res[i])$。
参考代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;
const int inf = 0x3f3f3f3f;
int n, m, k;
struct NODE
{
int x, y, val;
NODE() {}
NODE(int x, int y, int val)
{
this->x = x, this->y = y, this->val = val;
}
} a[MAXN];
int Y[MAXN];
struct BIT
{
ll c[MAXN];
int n;
void init(int n)
{
for (int i = 1; i <= n; i++)
c[i] = 0;
this->n = n;
}
int lowbit(int x)
{
return x & -x;
}
void update(int x, ll val)
{
while (x <= n)
{
c[x] = max(c[x], val);
x += lowbit(x);
}
}
ll query_max(int x)
{
ll ret = 0;
while (x)
{
ret = max(ret, c[x]);
x -= lowbit(x);
}
return ret;
}
} bit;
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= k; i++)
{
int x, y, val;
scanf("%d%d%d", &x, &y, &val);
a[i] = NODE(x, y, val);
Y[i] = y;
}
sort(Y + 1, Y + 1 + k);
m = unique(Y + 1, Y + 1 + k) - Y - 1;
// for (int i = 1; i <= Ycnt; i++)
// printf("%d ", Y[i]);
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, [](NODE x, NODE y) { return (x.x == y.x) ? x.y < y.y : x.x < y.x; });
bit.init(m);
ll ans = 0;
for (int i = 1; i <= k; i++)
{
ll res = bit.query_max(a[i].y) + a[i].val;
ans = max(ans, res);
bit.update(a[i].y, res);
}
printf("%lld\n", ans);
return 0;
}