P4995 跳跳!

    • 1.8K通过
    • 5.6K提交
  • 题目提供者 fstqwq 管理员
  • 评测方式 云端评测
  • 标签 排序 贪心
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    你是一只小跳蛙,你特别擅长在各种地方跳来跳去。

    这一天,你和朋友小 F 一起出去玩耍的时候,遇到了一堆高矮不同的石头,其中第 $i$ 块的石头高度为 $h_i$,地面的高度是 $h_0 = 0$。你估计着,从第 $i$ 块石头跳到第 $j$ 块石头上耗费的体力值为 $(h_i - h_j) ^ 2$,从地面跳到第 $i$ 块石头耗费的体力值是 $(h_i) ^ 2$。

    为了给小 F 展现你超级跳的本领,你决定跳到每个石头上各一次,并最终停在任意一块石头上,并且小跳蛙想耗费尽可能多的体力值。

    当然,你只是一只小跳蛙,你只会跳,不知道怎么跳才能让本领更充分地展现。

    不过你有救啦!小 F 给你递来了一个写着 AK 的电脑,你可以使用计算机程序帮你解决这个问题,万能的计算机会告诉你怎么跳。

    那就请你——会写代码的小跳蛙——写下这个程序,为你 NOIp AK 踏出坚实的一步吧!

    输入输出格式

    输入格式:

    输入一行一个正整数 $n$,表示石头个数。

    输入第二行 $n$ 个正整数,表示第 $i$ 块石头的高度 $h_i$。

    输出格式:

    输出一行一个正整数,表示你可以耗费的体力值的最大值。

    输入输出样例

    输入样例#1: 复制
    2
    2 1
    输出样例#1: 复制
    5
    输入样例#2: 复制
    3
    6 3 5
    
    输出样例#2: 复制
    49

    说明

    样例解释

    两个样例按照输入给定的顺序依次跳上去就可以得到最优方案之一。

    数据范围

    对于 $1 \leq i \leq n$,有 $0 < h_i \leq 10 ^ 4$,且保证 $h_i$ 互不相同。

    对于 $10\%$ 的数据,$n \leq 3$;

    对于 $20\%$ 的数据,$n \leq 10$;

    对于 $50\%$ 的数据,$n \leq 20$;

    对于 $80\%$ 的数据,$n \leq 50$;

    对于 $100\%$ 的数据,$n \leq 300$。

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