PDF《挖宝藏》

挖宝藏 问题描述: JP 不好好训练,又喜欢上了另一个游戏 --- 寻宝.

游戏里有 n 处宝藏,它们被埋在一个无限大的二维网格中.每个宝藏都有价值 Pi,位 置是 Xi,Yi. 如果网格(x,y)满足下面两个条件之一,则它是可挖掘的:

1、y=-1

2、(x-1,y+1),(x,y+1),(x+1,y+1)这三个方格都已经被挖掘了. 挖掘一个方格的代价为 1.当一个宝藏被挖掘出来时,就认为已经获得了它的价值. 请你帮 JP 求出所能得到的最大利润(价值-代价) . (可能一个宝藏也不挖,利润为 0) . 输入 第一行为 n(1