卧薪尝胆,厚积薄发。
POI2005 AUT-The Bus
Date: Sun Oct 14 20:57:24 CST 2018 In Category: NoCategory

Description:

一个网格图上有 $n$ 个点,每个点上有几个人,只能向左或向上走,最大化接的人数。
$1\leqslant n\leqslant 10^5$

Solution:

发现是一个二维偏序 $DP$ ,按 $x$ 排序 $+y$ 轴离散化树状数组优化 $DP$ 。

Code:


#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<map>
#include<cctype>
#include<cstring>
using namespace std;
int n;
inline int read()
{
register int res = 0,f = 1;
register char c = getchar();
while(!isdigit(c))
{
if(c == '-')f = -1;
c = getchar();
}
while(isdigit(c))
{
res = (res << 1) + (res << 3) + c - '0';
c = getchar();
}
return res * f;
}
#define MAXN 100010
struct point
{
int x,y,s;
}p[MAXN];
bool cmp_x(point a,point b){return (a.x != b.x ? a.x < b.x : a.y < b.y);}
int b[MAXN],tot = 0;
map<int,int> x;
int c[MAXN];
int lowbit(int x){return x & (-x);}
void add(int p,int x){for(int i = p;i <= tot;i += lowbit(i))c[i] = max(c[i],x);return;}
int query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res = max(res,c[i]);return res;}
int f[MAXN];
int main()
{
read();read();n = read();
for(int i = 1;i <= n;++i)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].s);
for(int i = 1;i <= n;++i)b[i] = p[i].y;
sort(b + 1,b + 1 + n);
for(int i = 1;i <= n;++i)
{
if(i == 1 || b[i] != b[i - 1])
x[b[i]] = ++tot;
}
for(int i = 1;i <= n;++i)p[i].y = x[p[i].y];
sort(p + 1,p + 1 + n,cmp_x);
int ans = 0;
for(int i = 1;i <= n;++i)
{
f[i] = query(p[i].y) + p[i].s;
add(p[i].y,f[i]);
ans = max(ans,f[i]);
}
cout << ans << endl;
return 0;
}
Copyright © 2020 wjh15101051
ღゝ◡╹)ノ♡