P2940 [USACO09FEB]音乐妖精The Leprechaun

    • 60通过
    • 141提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2009
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB


  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示


    Imagine Bessie's surprise as she spied a leprechaun prancing through the north pasture. Being no one's fool, she charged at the leprechaun at captured him with her prehensile hooves.

    'One wish, bovine one. That's all I have for cows,' he said.

    'Riches,' Bessie said dreamily. 'The opportunity for riches.'

    Leprechauns never grant precisely the easiest form of their captor's wishes. As the smoke cleared from the location of a loud explosion, a shimmering donut spun slowly over the verdant green fields.

    'I have made you a torus,' the leprechaun cooed. 'And on that torus is an N x N matrix (1 <= N <= 200) of integers in the range

    -1,000,000..1,000,000 that will determine the magnitude of your riches. You must find the sequence of contiguous integers all in one row, one column, or on one diagonal that yields the largest sum from among all the possible sequences on the torus.'

    Bessie pondered for a moment and realized that the torus was a device for 'wrapping' the columns, rows, and diagonals of a matrix so that one could choose contiguous elements that 'wrapped around' the side or top edge.

    Bessie will share the matrix with you. Determine the value of the largest possible sum (which requires choosing at least one matrix element).

    By way of example, consider the 4 x 4 matrix on the left below that has all the elements from one exemplary 'wrapped' diagonal marked:

    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

    The marked diagonal of the right-hand matrix includes two nines (the highest available number) and a six for a total of 24. This is the best possible sum for this matrix and includes only three of the four possible elements on its diagonal.



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

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






    * Line 1: A single integer: N

    * Lines 2..N+1: Line i+1 contains N space-separated integers that compose row i of the matrix


    * Line 1: A single integer that is the largest possible sum computable using the rules above


    输入样例#1: 复制
    8 6 6 1 
    -3 4 0 5 
    4 2 1 9 
    1 -9 9 -2 
    输出样例#1: 复制