首页 > 题解 > codeforce 13C Sequence

codeforce 13C Sequence


Little Petya likes to play very much. And most of all he likes to play the following game:

He is given a sequence of N integer numbers. At each step it is allowed to increase the value of any number by 1 or to decrease it by 1. The goal of the game is to make the sequence non-decreasing with the smallest number of steps. Petya is not good at math, so he asks for your help.

The sequence a is called non-decreasing if a1 ≤ a2 ≤ … ≤ aN holds, where N is the length of the sequence.

Input
The first line of the input contains single integer N (1 ≤ N ≤ 5000) — the length of the initial sequence. The following N lines contain one integer each — elements of the sequence. These numbers do not exceed 109 by absolute value.

Output
Output one integer — minimum number of steps required to achieve the goal.

Examples
input
5
3 2 -1 2 11
output
4
input
5
2 1 1 1 1
output
1

题意

给定一个序列,每次操作可以把某个数+1-1。要求把序列变成非降数列。而且要求修改后的数列只能出现修改前的数。

题解

定义两个数组a[i]=b[i],将b从小到大排序。

设f[i][j]表示前i个原数组数字,用不超过b[j]形成非降数列的最小花费,则可得出状态方程

$$f[i][j]=min(f[i][j-1],f[i-1][j]+|b[j]-a[i]|);(i>1,j>1);$$

$$f[1][1]=|b[1]-a[1]|;$$

$$f[1][j]=min(f[1][j-1],|b[j]-a[1]|)(j>1);$$

$$f[i][1]=f[i-1][1]+|b[1]-b[i]|(i>1);$$

然后滚动一下


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×