提高网站权重的作用,新艾尚网站建设推广,石家庄学网站建设,网址没封的来一个【题目来源】https://www.luogu.com.cn/problem/P4995【题目描述】你是一只小跳蛙#xff0c;你特别擅长在各种地方跳来跳去。 这一天#xff0c;你和朋友小 F 一起出去玩耍的时候#xff0c;遇到了一堆高矮不同的石头#xff0c;其中第 i 块的石头高度为 hi#xff0c;地…【题目来源】https://www.luogu.com.cn/problem/P4995【题目描述】你是一只小跳蛙你特别擅长在各种地方跳来跳去。 这一天你和朋友小 F 一起出去玩耍的时候遇到了一堆高矮不同的石头其中第 i 块的石头高度为 hi地面的高度是 h00。你估计着从第 i 块石头跳到第 j 块石头上耗费的体力值为 (hi-hj)^2从地面跳到第 i 块石头耗费的体力值是 (hi)^2。 为了给小 F 展现你超级跳的本领你决定跳到每个石头上各一次并最终停在任意一块石头上并且小跳蛙想耗费尽可能多的体力值。 当然你只是一只小跳蛙你只会跳不知道怎么跳才能让本领更充分地展现。 不过你有救啦小 F 给你递来了一个写着 AK 的电脑你可以使用计算机程序帮你解决这个问题万能的计算机会告诉你怎么跳。 那就请你——会写代码的小跳蛙——写下这个程序为你 NOIP AK 踏出坚实的一步吧【输入格式】 输入一行一个正整数 n表示石头个数。 输入第二行 n 个正整数表示第 i 块石头的高度 hi。【输出格式】 输出一行一个正整数表示你可以耗费的体力值的最大值。【输入样例1】 2 2 1【输出样例1】 5【输入样例2】 3 6 3 5【输出样例2】 49【数据范围】 对于 1≤i≤n有 0hi≤10^4且保证 hi 互不相同。 对于 10% 的数据n≤3 对于 20% 的数据n≤10 对于 50% 的数据n≤20 对于 80% 的数据n≤50 对于 100% 的数据n≤300。【算法分析】 本题思路就是排序后贪心对于数量任意的柱子应从先从地面跳到最高柱子再跳到最低柱子再跳到次高柱子……依次类推。 本质上是让小青蛙每次跳到和自己当前位置高度差最大的柱子上。【算法代码】
#include bits/stdc.h
using namespace std;const int maxn305;
long long h[maxn];
long long ans;int main() {int n;cinn;for(int i1; in; i) cinh[i];sort(h,hn1);int le0,rin;while(leri) {anspow(h[ri]-h[le],2);le;anspow(h[ri]-h[le],2);ri--;}coutansendl;return 0;
}/*
in:
3
6 3 5out:
49
*/
【参考文献】https://www.luogu.com.cn/problem/solution/P4995
