一、题目
给定长度为 N 的序列 A，构造一个长度为 N 的序列 B，满足：
1.B 非严格单调，即 B_1≤B_2≤…≤B_N 或 B_1≥B_2≥…≥B_N。 2.最小化 S=∑^N_{i=1}|A_i−B_i|。
只需要求出这个最小值 S。
输入格式
第一行包含一个整数 N。
接下来 N 行，每行包含一个整数 A_i。
输出格式
输出一个整数，表示最小 S 值。
数据范围
1≤N≤2000, 0≤A_i≤10^9
输入样例：
代码语言：javascript复制7
1
3
2
4
5
3
9输出样例：
代码语言：javascript复制3二、分析
此题有个结论：B_i 一定为序列 A 中的某个数字。
证明：
假设某个最优解序列如下图所示， A_i 为 原序列， A_i’ 为将原序列按从小到大排序后的序列。红点为 B 序列的分布。显然，每个 B_i 一定要么等于某个 A_i 或者不等于任何 A_i ，假设存在若干个 B_i 介于A’_ i 和 A’_ {i 1} 之间，即不等于任何 A_i，如图中粉色框框所示。假设这些 B_i 所对应的 A_i 的值 有x个值小于等于 A’_ i ，有 y个值大于等于 A’_ {i 1} ,分三种情况进行构造：
- x > y ,说明如果将粉色框整体向下移动，直到最小的红点等于
- x < y，则整体向上移动，使得最大的等于
x == y，则上移下移都一样，总和不会改变。
按照上述构造方法，可以将所有不在 A’_ i 上的点移动到某个 A_i’ 上，证毕。
上面对于构造方法的解释可能不太清晰，以下图为例，假设有A_ 1，A_ 2都小于 A’_ 1 , A_ 3 大于A’_ 2 , 即 x > y ，则将三个红点都向下移动等长的距离，直到最下面的红点碰到 A’_ 1 为止。则 |A_1−B_1| 和 |A_2−B_2| 都变小了， 虽然 |A_3−B_3| 变大了，但是整体还是更优，所以这是一种合理的构造方式。
利用这个结论我们可以用动态规划的思想：
dp[i][j] 表示已经考虑前 i 个 b_i 且最后一个以 a_j 结尾的最优解，则dp[i][j] = min(dp[i-1][k]) abs(a[i] – b[j]), 1 <= k <= ja[i] 存原数组， b[j] 存a数字排序后的数组，由于要满足 b_i <= b_{i 1}k 枚举下标 1-j 的所有可能，取最优解即可，这里需要 O(n) 。但是 j 每次是加一的，所以维护一个 1 到 j 的最小值，类似前缀和思想，可以将整个算法时间复杂度优化到 O(n) 。
三、代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
typedef long long LL;
LL dp[3333][3333], a[3333], b[3333];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i ) cin >> a[i], b[i] = a[i];
sort(b 1, b 1 n);
for (int i = 1; i <= n; i ) {
LL mmin = 1e18;//表示只考虑i-1个元素，结尾元素为b中的下标为1到j的最优解
for (int j = 1; j <= n; j ) {
mmin = min(mmin, dp[i - 1][j]);//先更新一下最优解
dp[i][j] = mmin abs(a[i] - b[j]);//dp[i][j] 就是只考虑前i-1种元素的最优解加上当前这个的abs
}
}
LL ans = 1e18;
for(int i = 1; i <= n; i ) ans = min(ans, dp[n][i]);
sort(b 1,b 1 n,greater<int>());//按照升序再来一次
for(int i = 1; i <= n; i ) {
LL mmin = 1e18;
for(int j = 1; j <= n; j ) {
mmin = min(mmin, dp[i-1][j]);
dp[i][j] = mmin abs(a[i] - b[j]);
}
}
for (int i = 1; i <= n; i ) ans = min(ans, dp[n][i]);
cout << ans;
}
