题目名称 276. [USACO Feb09] 神灯
输入输出 lepr.in/out
难度等级 ★☆
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 8
题目来源 Gravatarzqzas 于2009-02-22加入
开放分组 全部用户
提交状态
分类标签
USACO 基本
分享题解
通过:5, 提交:5, 通过率:100%
Gravatar梦那边的美好ET 100 0.072 s 0.48 MiB C++
Gravatar神犇 100 0.121 s 0.35 MiB C++
Gravatar神犇 100 0.141 s 0.24 MiB C++
Gravatar梦那边的美好ET 100 0.175 s 0.65 MiB C++
Gravatar神犇 100 0.177 s 0.24 MiB C++
关于 神灯 的近10条评论(全部评论)
认真的翻译(by 唯一一个做出来的)
(仅供借(chao)鉴(xi))(当然你要抄袭我也没办法)
你难以想象贝茜看到一只妖精在牧场出现时是多么的惊讶.她不是傻瓜,立即猛扑过去,用她那灵活的牛蹄抓住了那只妖精.
“你可以许一个愿望,傻大个儿!”妖精说.
“财富,”贝茜用梦游般的声音回答道, “我要获得财富的机会.”
妖精从来没有碰到过这么简单的愿望.他在地方划出一大块N×N(1≤N≤200)的方格,每个格子上写上_1,000,000到1,000,000之间的数字.他说: “在方格上朝一个方向行走,可以是行的方向,列的方向,斜对角的方向,一步只能走一格,所有你踩过的数字的和就是你的财富.”
贝茜请你来帮忙,找到一行、一列或一条对角线上找一段连续的数字,它们的和最大.由于妖精方格的神奇特性,沿着一个方向走,走到了边际,再一步跨过去可以“绕”到方格的对边出现.一行两端的格子是相邻的,一列两端的格子也是相邻的,甚至相邻两行的分别两端的格子也是相邻的(斜对角方向).
对于下图左边的方格,所有标记过的数字都在一条对角线上.
对于这个方格,能踩出来的最大的和是24,踩过的数字在右图中标记出来了
Gravatar神犇
2017-11-11 13:20 4楼
google翻译
小妖精[从BOI'98通过, 2008]
试想一下,贝茜的惊喜,因为她窥探一个妖精通过北牧场腾跃。因为没有人的傻瓜,她被控在妖精的抓住了他与她的抓握蹄子。
“一个心愿,牛之一。这就是我对牛, ”他说。
“财富”贝西朦胧地说。 “有机会的财富。 ”
妖精从来没有授予正是他们的俘虏的愿望最简单的形式。从一个响亮的爆炸位置硝烟散尽,一个闪闪发光的甜甜圈慢慢旋涂在青翠的绿色田野。
“我已经给你做了圆环, ”妖精叫唤。 “而在该圆环是一个N× N矩阵( 1 < = N < = 200 )的整数,范围
-1,000,000 1,000,000 ..这将决定您的幅度
财富。你必须找到连续的整数序列中的所有
一行,一列,或者在一个对角线的收益率从上环面所有可能的序列中最大的一笔。 “
贝西沉吟了一会儿,意识到圆环是一个设备为“包装”的列,行和矩阵的对角线,这样人们可以选择连续的元素, “缠”的侧面或顶部边缘。
贝茜将与您分享矩阵。确定的值
最大可能的总和(这要求选择的至少一个矩阵元素)。
通过举例的方式,考虑4×4矩阵的左侧下方具有从一个示例性的“包装”对角线标注的所有元素:
8 6 6 * 1 8 6 * 6 1
-3 4 0 5 * -3 4 0 5
4 * 2 1 9 4 2 1 9 *
1 -9 * 9 -2 1 -9 9 * -2
标记对角线右侧矩阵包括两个九
(可用的最高数)和一个6为总共24 。这
是最佳的总和为这个矩阵和仅包括3
在其对角线上的四个可能的因素。
题目名称: LEPR
输入格式:
*第1行:一个整数:不适用
*第2 .. N +1行:第i +1行包含N个用空格隔开的整数的
构成第i行的矩阵
输入样例(文件lepr.in ) :
4
8 6 6 1
-3 4 0 5
4 2 1 9
1 -9 9 -2
输出格式:
*第1行:一个整数,它是最大可能的总和可计算
使用上面的规则
输出样本(文件lepr.out ) :
24
Gravatarranto
2013-12-06 20:01 3楼
附议,但楼上××
Gravatar毕之
2013-11-06 18:49 2楼
虽然我能看懂 但是我不想看
Gravatar正确率超低的渣渣
2013-11-06 18:48 1楼

276. [USACO Feb09] 神灯

★☆   输入文件:lepr.in   输出文件:lepr.out   简单对比
时间限制:1 s   内存限制:128 MiB

Description

   你难以想象贝茜看到一只妖精在牧场出现时是多么的惊讶.她不是傻瓜,立即猛扑过去,用她那灵活的牛蹄抓住了那只妖精.

   “你可以许一个愿望,傻大个儿!”妖精说.

   “财富,”贝茜用梦游般的声音回答道,  “我要获得财富的机会.”

   妖精从来没有碰到过这么简单的愿望.他在地方划出一大块N×N(1≤N≤200)的方格,每个格子上写上_1,000,000到1,000,000之间的数字.他说:  “在方格上朝一个方向行走,可以是行的方向,列的方向,斜对角的方向,一步只能走一格,所有你踩过的数字的和就是你的财富.”

   贝茜请你来帮忙,找到一行、一列或一条对角线上找一段连续的数字,它们的和最大.由于妖精方格的神奇特性,沿着一个方向走,走到了边际,再一步跨过去可以“绕”到方格的对边出现.一行两端的格子是相邻的,一列两端的格子也是相邻的,甚至相邻两行的分别两端的格子也是相邻的(斜对角方向).

   对于下图左边的方格,所有标记过的数字都在一条对角线上.

           8  6  6* 1           8  6* 6  1
          -3  4  0  5*         -3  4  0  5
           4* 2  1  9           4  2  1  9*
           1 -9* 9 -2           1 -9  9*-2

对于这个方格,能踩出来的最大的和是24,踩过的数字在右图中标记出来了

Input

   第1行输入N,之后输入N行N列的矩阵.

Output

   输出最大的和.


Sample Input
4
8 6 6 1
-3 4 0 5
4 2 1 9
1 -9 9 -2

Sample Output
24