【2018ccpc区域赛网络赛】【hdu6447 YJJ's Salesman】【dp+离散化+树状数组/线段树优化】

71 阅读 0 评论 47 点赞

我是靠谱客的博主怡然曲奇，最近开发中收集的这篇文章主要介绍【2018ccpc区域赛网络赛】【hdu6447 YJJ's Salesman】【dp+离散化+树状数组/线段树优化】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接:

http://acm.hdu.edu.cn/showproblem.php?pid=6447

分析：二维坐标排序，x->大，y->小，由于我们每次走必须x，y均变大，那么相当于只要考虑排序后的y的值。从左往右考虑y，dp[i]=max（dp[j]）+val[i](i表示第i个点)，由于y的数据范围为1e9,需要离散化，然后用树状数组维护求最大。

代码：

#pragma warning(disable:4996)
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<double, int>pdi;
typedef long long ll;
#define CLR(a,b) memset(a,b,sizeof(a))
#define _for(i, a, b) for (int i = a; i < b; ++i)
const int mod = (int)1e9 + 7;
const long double eps = 1e-10;
const int maxn = 1e5 + 7;
const int INF = 0x3f3f3f3f;

struct node {
	ll x, y, z;
}k[maxn];

ll c[maxn];

ll lowbit(ll i) {
	return i & (-i);
}

ll getsum(ll x) {
	ll res = 0;
	while (x) {
		res =max(res, c[x]);
		x -= lowbit(x);
	}
	return res;
}

void add(ll x, ll v) {
	while (x <= 1e5) {
		c[x] = max(c[x], v);
		x += lowbit(x);
	}
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		CLR(c, 0);
		ll n;
		scanf("%lld", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%lld%lld%lld", &k[i].x, &k[i].y, &k[i].z);
		}
		sort(k + 1, k + 1 + n, [](const node &l, const node &r) {
			return l.y < r.y;
		});
		int cnt = 1;
		for (int i = 1; i <= n; ++i) {
			if (k[i].y != k[i + 1].y)
				k[i].y = cnt++;
			else
				k[i].y = cnt;
		}
		sort(k + 1, k + 1 + n, cmp);
		ll maxv = 0;
		for (int i = 1; i <= n; i++) {
			int tmp = getsum(k[i].y - 1) + k[i].z;//同行不能加，故要减1
			add(k[i].y, tmp);
		}
		printf("%lldn", getsum(n));
	}
}