P3431 [POI2005]AUT-The Bus

Link

简化题意：

给你一张网格图，每个点有其对应的权值，让你找出来一条横纵坐标都单调不降的路径，并最大化经过点的权值。

分析：

这是经典的二维数点或者二维偏序问题。

如果两维一直在变的话，我们不是很好处理，所以我们考虑对这些点排一下序，（按横纵坐标都可以）。

我一般按照横坐标来排序的。然后就变成了一维的最长不下降子序列问题。

设 \(f[i]\) 表示以 \(i\) 这个高度为结尾的经过路径的最大权值。

则有转移 \(f[i] = max(f[j] + a[i].w) j\leq i\)

因为公交车可以延着横坐标走，所以他也可以由 \(f[i]\) 转移过来。

此外还有一个要注意的点就是公交车沿着纵坐标竖着走，要先更新高度比较小的 \(f\) 值，（我就在这里卡了好几回）

那我们一开始的排序就可以以横坐标为第一关键字，纵坐标为第二关键字排序，这样方便我们 \(dp\)。

这样的直接 \(dp\) 的复杂度是 \(O(n^2)\) 的，可以考虑用树状数组或者线段树维护一下。

树状数组常熟小，代码短，也比较好写，所以我一般选择树状数组。

最后的答案就是 \(max(f[i])\), 另外不要忘记离散化哦。

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define int long long//不开long long 见祖宗·

const int N = 1e5+10;

int n,m,k,tr[N],b[N];

inline int read()

{

	int s = 0,w = 1; char ch = getchar();

	while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}

	while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}

	return s * w;

}

struct node

{

	int x,y,w;

}a[100010];

bool comp(node a,node b)

{

	if(a.x == b.x) return a.y < b.y;

	return a.x < b.x;

}

int lowbit(int x){ return x & -x; }

void chenge(int x,int val)

{

	for(; x <= N-5; x += lowbit(x)) tr[x] = max(tr[x],val);

}

int ask(int x)

{

	int res = 0;

	for(; x; x -= lowbit(x)) res = max(res,tr[x]);

	return res;

}

signed main()

{

	n = read(); m = read(); k = read();

	for(int i = 1; i <= k; i++)

	{

		a[i].x = read();

		a[i].y = read();

		a[i].w = read();

		b[i] = a[i].y;

	}

	sort(a+1,a+k+1,comp);//排序

	sort(b+1,b+k+1);

	int num = unique(b+1,b+k+1)-b-1;

	for(int i = 1; i <= k; i++) a[i].y = lower_bound(b+1,b+num+1,a[i].y)-b;//离散化

	for(int i = 1; i <= k; i++)

	{

		int res = ask(a[i].y);//树状数组优化dp

		chenge(a[i].y,res+a[i].w);

	}

	printf("%lld\n",ask(N-5));

	return 0;

}

巴特西

P3431 [POI2005]AUT-The Bus

简化题意：

最新文章

热门文章