/ TYWZ / 题库 /

17.10.6 Prob III - Function

17.10.6 Prob III - Function

题目描述

给定\(N\)个非负整数\(a_1, a_2 \cdots a_N\),定义\(N\)元函数\(f(x_1, x_2 \cdots x_N)\):
函数的定义域为\(N\)维整数空间,即\(x_i \in \mathbf{Z}, i=1,2 \cdots N\)。
(1)若\(x_1 \le x_2 \le \cdots \le x_N\),或者\(x_1 \ge x_2 \ge \cdots \ge x_N\),则:
\(f(x_1, x_2 \cdots x_N) = \displaystyle\sum_{i=1}^{N} \lvert a_i - x_i \rvert\)
(2)否则:
\(f(x_1, x_2 \cdots x_N) = +\infty\)
求该函数的最小值。

输入格式及数据规模

第一行是一个正整数\(N\);
第二行是\(N\)个非负整数\(a_1, a_2 \cdots a_N\)。
20%的数据:\(N \le 5\)
另外20%的数据:\(N \le 1000, \phantom{x} a_i \le 1000\)
另外20%的数据:\(N \le 100\)
100%的数据:\(N \le 2000, \phantom{x} a_i \le 10^9\)。

输出格式

一个整数,该函数的最小值。

样例

input

7
1 3 2 4 5 3 9

output

3

限制

Time limit: 1 sec
Memory limit: 128 megabytes

来源

From PKU Online Judge (POJ 3666)

信息

难度
9
分类
动态规划 点击显示
标签
(无)
递交数
9
已通过
2
通过率
22%
上传者

相关