P4995 跳跳！——贪心

P4995 跳跳！——贪心

跳跳！

题目描述

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

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

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

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

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

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

输入格式

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

输入第二行 n n n 个正整数，表示第 i i i 块石头的高度 h i h_i hi​。

输出格式

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

样例 #1

样例输入 #1

2
2 1

样例输出 #1

5

样例 #2

样例输入 #2

3
6 3 5

样例输出 #2

49

提示

样例解释

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

数据范围

对于 1 ≤ i ≤ n 1 leq i leq n 1≤i≤n，有 0 < h i ≤ 1 0 4 0 < h_i leq 10 ^ 4 0<hi​≤104，且保证 h i h_i hi​ 互不相同。

对于 10 % 10% 10% 的数据， n ≤ 3 n leq 3 n≤3；

对于 20 % 20% 20% 的数据， n ≤ 10 n leq 10 n≤10；

对于 50 % 50% 50% 的数据， n ≤ 20 n leq 20 n≤20；

对于 80 % 80% 80% 的数据， n ≤ 50 n leq 50 n≤50；

对于 100 % 100% 100% 的数据， n ≤ 300 n leq 300 n≤300。

分析

1. 首先分析此题的贪心策略，样例1太简单看不太出来，看样例2 ，6 3 5，起点先跳到6，耗费体力6*6，然后6跳到3耗费体力：(6-3) * (6-3)，最后3跳到5耗费体力：(5-3) * (5-3) ;共消耗体力49；然后开始想，调换顺序，按照3 6 5，按顺序跳，发现不是最优解，然后分析耗费体力的两个表达式： ( h i − h j ) 2 (h_i - h_j) ^ 2 (hi​−hj​)2、 ( h i ) 2 (h_i) ^ 2 (hi​)2；可以发现起点直接跳到最高的石头，能使第一跳最优，然后发现两个石头的差值越大，那耗费体力就越多；所以此题和：P1094 [NOIP2007 普及组] 纪念品分组——贪心一样，尽可能让大的结合小的贪心问题；
2. 贪心策略：起点直接跳到最高的石头，然后最高跳最低的石头，然后最低的石头跳次高的石头…，就这样左右横跳，尽可能让大的结合小；
3. 细节：①由于起点应该直接跳到最高，所以a[0]=0当起点，数组从1开始存数；②while循环条件，不能是i<=j，因为i==j时已经站在最后一块石头了，不用跳了（这个可以根据样例调，也不必太纠结）；③看数据范围 0 < h i ≤ 1 0 4 0 < h_i leq 10 ^ 4 0<hi​≤104，那么ans累加几次，就会爆int了，所以有时候wa了，可以试着调longlong；④i++,j–，上题是一块进行的，这题是模拟此题，当跳到后面，需要先i++，因为该跳到前面的次低石头，更新前面的石头；

#include<bits/stdc++.h>using namespace std;int n;
long long ans;
int a[305];int main() {cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}sort(a + 1, a + 1 + n);//首尾指针，左右横跳int i = 0, j = n;while (i < j) {//i==j时已经站在最后一块石头了，不用跳了//前面跳到后面,起始直接从平地a[0]=0跳到最后一块石头ans += pow(a[j] - a[i], 2);//下一跳，要跳到前面新的石头了，更新前面的石头i++;//从后面跳到前面ans += pow(a[j] - a[i], 2);//更新后面的石头j--;}cout << ans;return 0;
}