1333: 亮度调节

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:0 通过:0

题目描述

    z老师很烦恼:偌大的机房空无一人,一排电脑屏幕却还亮着。z老师更烦恼的是:这排电脑屏幕的亮度并不统一,有些很亮,有些很暗。“这不好……至少要把亮度调整一下吧!
    
    z老师面前有一排 n 台电脑,每一台电脑都有一个用整数表示的亮度值ai(可能为负数)。
    在z老师走进机房时,他并不烦恼。
    对于任意两台电脑,如果左边的亮度值大于右边的(i < j,ai > aj),他就会获得 L 的烦恼值。
    z老师可以进行的操作是,把一台电脑的亮度值修改为它的相反数。
    他可以修改任意多次,以使得自己最终的烦恼值最小,而你需要求出这个最小值。

输入格式

    第 1 行,一个整数 n 表示有 n 台电脑。
    第 2 行共 n 个整数 ai ,表示从左往右第 i 台电脑的初始亮度值。
    
    数据范围要求:
    对于30%的数据,n≤18
    对于另外5%的数据,|ai| = 1;
    对于另外20%的数据,|ai| ≤ 1
    对于70%的数据,n≤5 x 103(包含前面两档部分分);
    对于100%的数据,1≤n≤106,0≤|ai| ≤ 105

输出格式

    一行一个整数,表示最小的烦恼值。

输入样例 复制

18
-1 -7 0 -2 -1 -7 5 1 1 6 -9 2 -7 9 0 -5 0 5

输出样例 复制

36

分类标签