HDU 6447 - YJJ's Salesman - [树状数组优化DP][2018CCPC网络选拔赛第10题]
2021-07-14 04:08
标签：数组 ons rom mat 状态 sum 题目 cat count 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6447 Problem Description Input Output Sample Input Sample Output Source 题意： 从 $(0,0)$ 往 $(10^9,10^9)$ 走，每次只能从 $\left( {x,y} \right)$ 走到 $\left( {x + 1,y} \right)$ 或者 $\left( {x,y + 1} \right)$ 或者 $\left( {x + 1,y + 1} \right)$，不能折返，不能走重复的路， 在地图上分布着一些村庄，给出村庄的坐标 $\left( {x,y} \right)$ 和 $v$ 值，当且仅当你从 $\left( {x - 1,y - 1} \right)$ 走到村庄时，你才可以获得 $v$，求最大能获得多少 $v$。 题解： 显然，假设我走到了某一个村庄 $\left( {x_0,y_0} \right)$，那么只有在 $x \ge x_0 + 1$ 且 $y \ge y_0 + 1$ 范围内的村庄，能使得我的 $v$ 值进一步增加， 换句话说，我走到了某一个村庄 $\left( {x_0,y_0} \right)$，我上一个走到的“有意义的”村庄必然是在 $x \le x_0 - 1$ 且 $y \le y_0 - 1$ 的范围内的， 那么我就要在 $x \le x_0 - 1$ 且 $y \le y_0 - 1$ 的范围内找到某个村庄，我走到该村庄时，我获得的 $v$ 值时最大的， 故，我们假设 $dp\left[ i \right]$ 为走到村庄 $i$ 时能获得的最大的 $v$，则状态转移方程为： $dp\left[ i \right] = \max \left( {dp\left[ j \right] + v\left[ i \right]} \right)$，其中村庄 $j$ 的坐标 $\left( {x,y} \right)$ 满足 $x \le x_0 - 1$ 且 $y \le y_0 - 1$ 那么，对于每个村庄，要能 $O\left( {\log n} \right)$ 获得某区域内的最大值，同时也要能 $O\left( {\log n} \right)$ 的某区域内的最大值，自然而然想到树状数组…… HDU 6447 - YJJ's Salesman - [树状数组优化DP][2018CCPC网络选拔赛第10题] 标签：数组 ons rom mat 状态 sum 题目 cat count 原文地址：https://www.cnblogs.com/dilthey/p/9539618.html
YJJ is a salesman who has traveled through western country. YJJ is always on journey. Either is he at the destination, or on the way to destination.
One day, he is going to travel from city A to southeastern city B. Let us assume that A is (0,0) on the rectangle map and B (109,109). YJJ is so busy so he never turn back or go twice the same way, he will only move to east, south or southeast, which means, if YJJ is at (x,y) now (0≤x≤109,0≤y≤109), he will only forward to (x+1,y), (x,y+1) or (x+1,y+1).
On the rectangle map from (0,0) to (109,109), there are several villages scattering on the map. Villagers will do business deals with salesmen from northwestern, but not northern or western. In mathematical language, this means when there is a village k on (xk,yk) (1≤xk≤109,1≤yk≤109), only the one who was from (xk?1,yk?1) to (xk,yk) will be able to earn vk dollars.(YJJ may get different number of dollars from different village.)
YJJ has no time to plan the path, can you help him to find maximum of dollars YJJ can get.
The first line of the input contains an integer T (1≤T≤10),which is the number of test cases.
In each case, the first line of the input contains an integer N (1≤N≤105).The following N lines, the k-th line contains 3 integers, xk,yk,vk (0≤vk≤103), which indicate that there is a village on (xk,yk) and he can get vk dollars in that village.
The positions of each village is distinct.
The maximum of dollars YJJ can get.
1
3
1 1 1
1 2 2
3 3 1
3
2018中国大学生程序设计竞赛 - 网络选拔赛
文章标题：HDU 6447 - YJJ's Salesman - [树状数组优化DP][2018CCPC网络选拔赛第10题]
文章链接：http://soscw.com/index.php/essay/104949.html