本文主要是介绍【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++;elsek[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;//同行不能加，故要减1add(k[i].y, tmp);}printf("%lld\n", getsum(n));}
}
这篇关于【2018ccpc区域赛网络赛】【hdu6447 YJJ's Salesman】【dp+离散化+树状数组/线段树优化】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
