[JSOI2010] 挖宝藏
题目描述
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$,表示宝藏数量。
接下来 $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$。