A2537. 挖宝藏
编程题
省选/NOI-
知识点
题目描述
JP 不好好训练，又喜欢上了另一个游戏——寻宝。
游戏里有 $n$ 处宝藏，它们被埋在一个无限大的二维网格中。每个宝藏都有价值 $P_i$，位置是 $(x_i,y_i)$。
如果网格 $(x,y)$ 满足下面两个条件之一，则它是可挖掘的：
- $y=-1$。
- $(x-1,y+1),(x,y+1),(x+1,y+1)$ 这三个方格都已经被挖掘了。
挖掘一个方格的代价为 $1$。当一个宝藏被挖掘出来时，就认为已经获得了它的价值。请你帮 JP 求出所能得到的最大利润，也即价值减代价。（可能一个宝藏也不挖，利润为 $0$）
游戏里有 $n$ 处宝藏，它们被埋在一个无限大的二维网格中。每个宝藏都有价值 $P_i$，位置是 $(x_i,y_i)$。
如果网格 $(x,y)$ 满足下面两个条件之一，则它是可挖掘的：
- $y=-1$。
- $(x-1,y+1),(x,y+1),(x+1,y+1)$ 这三个方格都已经被挖掘了。
挖掘一个方格的代价为 $1$。当一个宝藏被挖掘出来时，就认为已经获得了它的价值。请你帮 JP 求出所能得到的最大利润，也即价值减代价。（可能一个宝藏也不挖，利润为 $0$）
输入格式
第一行为 $n$，表示宝藏数量。
接下来 $n$ 行，每行三个整数 $x_i,y_i,P_i$ 表示宝藏的位置和价值。
接下来 $n$ 行，每行三个整数 $x_i,y_i,P_i$ 表示宝藏的位置和价值。
输出格式
一行一个整数，表示最大利润。
输入输出样例
输入 #1
5 1 -1 2 0 -1 2 4 -1 1 3 -1 2 2 -1 2
输出 #1
4
说明/提示
### 样例解释 1
挖 $1,2,4,5$ 号宝藏，价值为 $8$，花费代价为 $4$，所以利润为 $4$。可以证明没有更优的方案。
### 数据范围
对于 $30\%$ 的数据，$n\leq 15$。
对于 $50\%$ 的数据，$-10^3\leq y_i\leq 0$。
对于 $100\%$ 的数据，$n\leq 10^3,-10^4\leq x_i\leq 10^4,-10^4\leq y_i<0,1\leq P_i\leq 10^6$。
挖 $1,2,4,5$ 号宝藏，价值为 $8$，花费代价为 $4$，所以利润为 $4$。可以证明没有更优的方案。
### 数据范围
对于 $30\%$ 的数据，$n\leq 15$。
对于 $50\%$ 的数据，$-10^3\leq y_i\leq 0$。
对于 $100\%$ 的数据，$n\leq 10^3,-10^4\leq x_i\leq 10^4,-10^4\leq y_i<0,1\leq P_i\leq 10^6$。