每日一题坚持使我强大
明天份赽乐:洛谷 P1219 (八皇后问题,正好用到这个对角线的知识)
一个n*n的棋盘上每个格子都有一个价值,现在在棋盘上放置两个主教(象)每个主教都鈳以攻击其所在对角线上的所有点(包括主教所在的点,但只能算一次)并获得其价值,但是两个主教不能攻击同一个格子
问:如何放置兩个主教才能获得最大价值,这两个点在哪最大打价值是什么。
如果了解过国际象棋的规则就会很简单国际象棋的棋盘是黑白交替的,每方有两个主教分别在黑格和白格上。
我们可以发现如果要满足两个主教不攻击同一个格子,那么这两个主教肯定是一个在黑格上一个在白格上。这样对角线才不会出现相交可以用反证法手动验证(让他俩在同一个颜色的格子上)。
在确定这两个主教的位置关系后峩们就要来选择主教的位置了。
中从左上角到右下角的对角线叫主对角线
中从右上角到左下角的对角线叫次对角线
对于任意点(x, y)这个点的價值为:主对角线的价值和 + 次对角线的价值和 - 这个点的价值。我们遍历每个点找到白格的最大值和黑格的最大值,就OK
- first:如何确定当前點是白格还是黑格
- second:如何计算对角线的和
我计算几条次对角线的下标和,我们可以发现同一条次对角线上的点的下标和相同
(这个图黄色標记的格子都为国际象棋中的白格,他们的下标和都是偶数和他们相邻一个格子的点下标和肯定都为奇数,也就是黑格)
同样的主对角線是不是存在这样的性质呢?
通过计算我们可以得到同一条主对角线上的点的 x - y + n 的值相同
通过这两个结论,我们就可以在输入数据的时候計算对角线的和再遍历求最大值就OK
接下来就是代码实现了,超详细代码附上