F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:五月份月赛定于5.27日12:30--17:30,欢迎大家来玩! 2:关于OJ的注册可看https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671
Problem 5059. -- 前鬼后鬼的守护

5059: 前鬼后鬼的守护

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 80  Solved: 49
[Submit][Status][Discuss]

Description

八云紫的式神八云蓝有一张符卡名为[式神-前鬼后鬼的守护],这张符卡的弹幕为BOSS从两侧向自机发射大玉,大
玉后面跟着一些小玉,形成一个“V”字型的弹幕。然鹅兰大人觉得这个弹幕还能再美观一些,她想让自己的弹幕
能从左向右发射,于是她就开始了行动。
[式神-前鬼后鬼的守护]由 N波弹幕组成,每波弹幕都有一个落到板底的位置,第i波弹幕的落地位置为Xi。
为了让弹幕能从左到右落地,蓝妈需要改变一些弹幕的落地位置,使得改变后的落地位置的坐标不递减,即
。然鹅改变弹幕的方向是很累的,蓝妈每将一波弹幕的坐标增加或减少1,就会花费一单位的能量,即
蓝妈想确定一个最终的修改方案使得他花费的能量最少,于是她将设计修改方案的任务交给了自己的式神八云橙。
这可急坏了我们的橙喵,她只是连曼哈顿距离都不会算的年幼式神,你能帮助她完成这个任务吗?

Input

输入文件第一行为一个正整数N ,意义如题目所示。接下来一行N个正整数,第i个整数代表Xi 。
N<=5*10^5,Xi<=10^9

Output

输出一个整数,为最小消耗的能量值。

Sample Input

7
1 3 2 4 5 3 9

Sample Output

3
将第二波弹幕的落地位置由3改为2 ,花费为1 ,将第六波由3 改为5 ,花费为2 ,总花费为1+2=3 ,形成了一个
不下降序列:1,2,2,4,5,5,9为最优解(不一定为唯一最优解)

HINT

Source

[Submit][Status][Discuss]

HOME Back