TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5411
  • 题目
  • P5411【继续欢乐】赚钱的游戏·第K大
    限制 : 时间限制 : - MS   空间限制 : - KB
    问题描述

    \(n\) 堆石子排成一列,每堆石子数量可以是负数。

    一次游戏的过程是每次选择两堆相邻的石子,如果石子数量分别为 \(x,y\) 则合并时可以获得 \(xy\) 元人民币,将合并后的这堆石子放回原来的位置,一直操作直到只剩下一堆石子。玩游戏的人很机智,总是按照获得总人民币最多的方式进行游戏。

    如果选择范围 \(L,R\) 进行游戏,最多可以获得 \(f(l,r)\) 元,请计算出获得人民币前 \(k\) 多的范围,以及每个范围可以获得的人民币数量。如果两个范围获得的人民币一样多,优先输出 \(l\) 较小的范围;如果 \(l\) 也相等,优先输出 \(r\) 较小的。

    输入格式

    输入共两行。

    第一行两个整数 \(n,k\) ,表示石子的数量和需要计算前 \(k\) 大的方案。

    第二行 \(n\) 个整数,表示每堆石子的数量 \(a_1,a_2,\dots,a_n\)

    输出格式

    输出共 \(k\) 行。

    每行输出三个数 \(l,r,f(l,r)\),第 \(i\) 行表示第 \(i\) 大的方案。

    样例输入

    6 8
    2 1 2 1 -1 -1

    样例输出

    1 4 13
    1 3 8
    1 5 7
    2 4 5
    1 2 2
    1 6 2
    2 3 2
    3 4 2

    提示

    $1\leq n\leq 105, 1\leq k\leq \min \left\{105, \frac {n(n+1)}2\right\}, |a_i|\leq 500$


    来源  感谢nodgd命题