Skip to content

11270: 【原1270】盾盾吃果果

题目

题目描述

author: Cheezer 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1270

Description

盾盾最喜欢吃果果了。今天,盾盾妈给他带来了一大袋果果,他准备全部吃完。他把每个果果从1~n编号,每个果果有一个喜爱程度ai,但是盾盾特别喜欢刺激,也就是如果先吃到一个不喜欢的果果,再吃一个喜欢的果果,他就会非常高兴。现在可以用一个值F表示盾盾的高兴程度。盾盾要求在给定n个果果及每一个果果的喜欢程度ai的条件下,求一个这些果果的排列bi (n个元素,1<=bi<=n,且对于i<>j,bi<>bj),使得我们定义的函数 \( F=∑_{j=2}^n max⁡(a[b[j]]-a[b[j-1]],0) \) 最大。请你求出这个最大值。

Input Format

输入包括n+1行。

第一行为n,接下来1行为n个数ai,用空格分开。

100%: N<=100000,Ai<=10^9,F在int范围内

Output Format

一个数,表示最大的函数值F。

Sample Input

5
5 9 3 5 4

Sample Output

7

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!