P3016 [USACO11FEB]三角形The Triangle

    • 29通过
    • 128提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2011 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    For her spectacular milk output for the previous month, Farmer John has awarded Bessie a prize -- with a twist. He has given her a triangular grid with N (1 <= N <= 700) rows (whose lengths vary from 1 through N, of course). Row i of the the grid has i values labeled v_ij (-1,000,000,000 <= v_ij <= 1,000,000,000) where j is in the range 1..i.

    Bessie chooses a sub-triangle whose side length is at least K (1 <= K <= 20; 1 <= K <= N) within the triangular grid. The sub-triangle is another triangular grid which might be oriented the same as the original triangle or might be 'upside down' with its shorter rows on the bottom instead of the top.

    After she chooses her sub-triangle, Farmer John will take the average of all the numbers in the sub-triangle, discarding the digits to the right of the decimal point, and give her that many gold coins (or take that many gold coins from her if the number is negative). Naturally, Bessie would like to maximize her prize (or minimize her loss). Help her solve this problem.

    By way of example, Bessie is given this triangular grid with N = 3 rows and must choose a sub-triangle with a side length of at least K = 2. A graphical representation of the triangle is shown below:

        / \
       / 5 \
      /-8  4\
     /2 -3  6\
     ---------

    She could choose any of five valid sub-triangles (one of which is the entire original triangle):

                                                       /\
        / \         / \        / \         / \        /5 \       
       / 5 \       / \5\      / 5 \       / 5/\      /----\    
      /-8  4\     /-8 \4\    /-8  4\     /-8/ 4\    /\-8 4/\ 
     /2 -3  6\   / 2 -3\6\  /-------\   / 2/-3 6\  / 2\-3/6 \ 
     ---------   ---------  -2  -3  6   ---------  ----------  
      entire      lower        top          lower     upside
     triangle     left                      right      down

    The one that is lined below is the one with the highest average:

        / \
       / 5/\
      /-8/ 4\
     / 2/-3 6\
     ---------

    The average of this sub-triangle is (4+6-3)/3, which is about

    2.3333...; without the fraction, the answer is 2.

    Help Bessie calculate the maximum amount of coins which she could receive.

    TIME LIMIT: 2 seconds

    MEMORY LIMIT: 32 MB

    有一个n(1<=n<=700)行的等腰三角形,里面有很多数(-1,000,000,000 <= 数 <= 1,000,000,000),现在可以选择边长至少为k(1<=k<=20,1<=k<=n),至多为2k的相似等腰三角形,并且可以倒着选,比如样例可以有这些选择方法:

    样例:

                                                       /\
        / \         / \        / \         / \        /5 \       
       / 5 \       / \5\      / 5 \       / 5/\      /----\    
      /-8  4\     /-8 \4\    /-8  4\     /-8/ 4\    /\-8 4/\ 
     /2 -3  6\   / 2 -3\6\  /-------\   / 2/-3 6\  / 2\-3/6 \ 
     ---------   ---------  -2  -3  6   ---------  ----------  
      entire      lower        top          lower     upside
     triangle     left                      right      down

    最后问你可以得到的最大平均值为多少(平均值:选出的三角形的累加和div选出个数)

    输入输出格式

    输入格式:

    * Line 1: Two space-separated integers: N and K

    * Lines 2..N+1: Line i+1 will contain i space-separated integers: v_ij

    输出格式:

    * Line 1: The maximum number of coins that Bessie can receive (or, if negative, the best she can do for her loss).

    输入输出样例

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

    说明

    感谢 zzkksunboy 提供翻译。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。