当前位置:首页 > 枚举 > 正文
P7472吃豆人[2021NOIOnline]
82+

题目大意:一个n*n矩阵,选出两个极大的斜矩形,要求边框包含的数字之和最大,最大值是多少?

题目背景

数据旨在卡掉尽可能多的错解,因此错解可能获得较高分数。

题目描述

有一个 列的正方形点阵,左上角点坐标为 ,右下角点坐标为

点阵中每个整点上都有数量不一的豆子,坐标为 的点上有 个豆子。

你可以放置吃豆人,可以将点阵中任意的整点作为吃豆人的初始位置,再给定左上、左下、右上、右下之一作为吃豆人的初始方向。

吃豆人会不断沿初始方向行进,吃光遇到的所有豆子,直到碰到点阵的边界,此时:

  1. 如果吃豆人处于正方形点阵四个角之一的位置,那么就会停止行动;
  2. 否则,吃豆人的行进路线将以这条边界为镜面发生反射,下图展示了一个路径某两次发生反射的例子:

现在,你需要放置两个吃豆人,求两个吃豆人最多共能吃到多少个豆子?注意同一个豆子只能被吃一次。

输入格式

第一行包含一个整数 ,表示点阵大小。

接下来 行,每行包含 个整数,其中第 行第 个整数表示

输出格式

输出一行一个整数,表示两个吃豆人最多共能吃到的豆子数量。

输入输出样例

输入 #1
4
20 1 19 2
3 18 4 17
16 5 15 6
7 14 8 13
输出 #1
132

说明/提示

样例 1 解释

位置放置吃豆人,初始方向分别为右下和左下,即可吃到位于 位置上的豆子,总个数为 , 达到最大,路径分别如下图绿线和红线所示:

数据范围

对于 的数据,

对于 的数据:

对于 的数据:

解题思路

显然,反射形成的路径,必然是一个矩形,求矩形边框数字之和,可以用前缀和——斜着的前缀和。

如何枚举矩形?枚举其中一个顶点即可,其他三个顶点可以算出来,因为斜边有规律,如i+j相等,获赞j-i相等。

接下来就是算重合点,至多4个,举一个例子,逐个解决即可。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,

P7472吃豆人[2021NOIOnline]:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter