YJJ's Salesman HDU - 6447（线段树单点更新+DP思想）_LBJHan的博客-程序员宅基地

YJJ's Salesman

题意：一个1e9*1e9的地图，要求由(0, 0) -> (1e9, 1e9)；只能向下，向右，向右下移动；地图中有n个点，有宝藏，只有从该点的左上方移动过来才能拿走宝藏，问最多能拿走多少宝藏；

本题和之前做过的一个数星星题有点相似，题目链接：POJ - 2352

根据题意可知在每一个点能拿到的宝藏一定是其左上方的点，那么就是找这个点的左上方的点的宝藏总和；可以用线段树维护；怎么维护呢？

把y坐标当做需要维护的区间值，然后向线段树里插点，计算的时候就是计算区间[1, y]的值，那么。x坐标一定是由小到大向线段树里插才不会漏掉点，而对于y坐标，要由大到小插点才不会将在计算到同一行的点；这样就只记录了左上方的点；插点的时候插入的值不单单是将要插入的点的宝藏值，还包括有左上方走过来得到的最大宝藏；因为并不是左上方的所有点的宝藏都能拿到手，只计算在左上方能拿到的最大宝藏就ok了，确实DP的思想；

再一点，本体需要离散化；

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
struct point{
	int x, y, val;
	bool operator < (const point& a)const{
		if(x==a.x) return y>a.y;
		return x<a.x;
	}
}p[maxn];
int t[maxn];
struct node{
	int l, r, val;
}tr[maxn<<2];
void pushup(int m){	
	tr[m].val=max(tr[m<<1].val, tr[m<<1|1].val);
}
void build(int m, int l, int r){
	tr[m].l=l;
	tr[m].r=r;
	tr[m].val=0;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(m<<1, l, mid);
	build(m<<1|1, mid+1, r);
}
void updata(int m, int x, int val){
	if(tr[m].l==x&&tr[m].r==x){
		tr[m].val=max(tr[m].val, val);
		return;
	}
	int mid=(tr[m].l+tr[m].r)>>1;
	if(x<=mid) updata(m<<1, x, val);
	else updata(m<<1|1, x, val);
	pushup(m);
}
int query(int m, int l, int r){
	if(tr[m].l==l&&tr[m].r==r){
		return tr[m].val;
	}
	int mid=(tr[m].l+tr[m].r)>>1;
	if(r<=mid) return query(m<<1, l, r);
	else if(l>mid) return query(m<<1|1, l, r);
	else return max(query(m<<1, l, mid), query(m<<1|1, mid+1, r));
}
int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		int n;
		scanf("%d", &n);
		for(int i=1; i<=n; i++){
			scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].val);
			t[i]=p[i].y;
		}
		sort(t+1, t+1+n);
		int cnt=unique(t+1, t+1+n)-(t+1);
		for(int i=1; i<=n; i++){
			p[i].y=lower_bound(t+1, t+1+n, p[i].y)-t;
		}
		sort(p+1, p+1+n);
		build(1, 1, n);
		int ans=0, temp=0;
		for(int i=1; i<=n; i++){
			if(p[i].y==1){
				temp=0;
				updata(1, 1, p[i].val);
			}
			else{
				temp=query(1, 1, p[i].y-1);
				updata(1, p[i].y, temp+p[i].val);
			}
			ans=max(ans, temp+p[i].val);
		}
		printf("%d\n", ans);
	}
	return 0;
}

本文链接：https://blog.csdn.net/Sirius_han/article/details/82114301

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

机器学习实验（十一）：基于WiFi fingerprints用自编码器(Autoencoders)和神经网络(Neural Network)进行定位_2(keras版)_autoencoder能做定位吗_风雪夜归子的博客-程序员宅基地

深度学习caffe平台--train_val.prototxt文件中数据层及参数详解_白话先生的博客-程序员宅基地

转载自己：http://www.cnblogs.com/denny402/p/5070928.html要运行caffe，需要先创建一个模型（model)，如比较常用的Lenet,Alex等，而一个模型由多个屋（layer）构成，每一屋又由许多参数组成。所有的参数都定义在caffe.proto这个文件中。要熟练使用caffe，最重要的就是学会配置文件（prototxt）的编写。层有

apache httpd.conf 路径配置_apache httpd.conf路径_worldzhy的博客-程序员宅基地

DocumentRoot "/Users/worldzhy/Documents/InceptionPad" # # Possible values for the Options directive are "None", "All", # or any combination of: # Indexes Includes FollowSymLinks Sym

mysql my.ini 密码_安装完mysql没找到my.ini，还有设置的登陆密码没有用_不知盗的博客-程序员宅基地

只有一个my-default.ini# For advice on how to change settings please see# http://dev.mysql.com/doc/refman/5.7/en/server-configuration-defaults.html# *** DO NOT EDIT THIS FILE. It's a template which will be...

好程序员web前端教程分享JavaScript简写方法_好程序员IT的博客-程序员宅基地

今天好程序员web前端教程为大家分享JavaScript简写方法，小伙伴们快来看一看吧。1.三元操作符当想写if...else语句时，使用三元操作符来代替。constx=20;letanswer;if(x>10){answer='isgreater';}else{answ...

自定义mybatis拦截器拦截sql_spring_cainiao的博客-程序员宅基地

配置文件装载拦截器拦截器代码：import com.alibaba.fastjson.JSONObject;import lombok.extern.slf4j.Slf4j;import org.apache.commons.lang3.StringUtils;import org.apache.ibatis.executor.Executor;import org.apache.ibatis.mapping.BoundSql;import org.apache.ibatis.map