跳跳！

传送锚点：

www.luogu.com.cn

题目描述

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

这一天，你和朋友小 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

样例输入 #1

2
2 1

样例输出 #1

5

样例 #2

样例输入 #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\)。

思路

此题注意一开始在地面，要使体力消耗最大，则需高度最高的石头，在从最高的石头跳到最矮的石头，再从最矮的石头跳到第二高的石头……以此类推
此题要开long long，用数组height记录石头高度，再将height排序，count记录跳了几座山，pre为之前所处的高度
循环，i遍历左侧石头，j遍历右侧石头，i > j时说明所有石头都已跳过，
若跳过的山数量为奇数(即count&1)，xp += (ll)((height[j] - pre) * ( height[j] - pre));
若跳过的山数量为偶数(即count&1==false)，xp += (ll) ((height[i] - pre) * ( height[i] - pre));

code

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int main() {
   int n;
   cin >> n;
   vector<int> height(n);//石头高度
    for (int i = 0; i < n; ++i) {
        cin >> height[i];
    }
    sort(height.begin(), height.end());
    ll xp = 0;//体例值
    int pre = 0;//之前所处的高度 注意：一开始青蛙在地面上
    int i = 0, j = n-1;
    int count = 0;//记录跳了几座山
    while(i <= j){
        count ++;
        if(count & 1){
            xp += (ll)((height[j] - pre) * ( height[j] - pre));
            pre = height[j--];
        }else{
            xp += (ll) ((height[i] - pre) * ( height[i] - pre));
            pre = height[i++];
        }

    }
    cout << xp;
}