线性dp，优化记录，273. 分级

273. 分级

273. 分级 - AcWing题库

给定长度为 N 的序列 A，构造一个长度为 N 的序列 B，满足：

1. B 非严格单调，即 B1≤B2≤…≤BN 或 B1≥B2≥…≥BN。
2. 最小化 S=∑Ni=1|Ai−Bi|。

只需要求出这个最小值 S。

输入格式

第一行包含一个整数 N。

接下来 N 行，每行包含一个整数 Ai。

输出格式

输出一个整数，表示最小 S 值。

数据范围

1≤N≤2000
0≤Ai≤106

输入样例：

7
1
3
2
4
5
3
9

输出样例：

3

解析

 题目非常好，但我还没吃透，理解的不够深，解析先不写，现附上acwing的题解，等完全掌握后再写解析

AcWing 273. 分级 - AcWing

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>using namespace std;
typedef long long LL;
const int N = 2e3 + 5;
int  n;
int a[N], b[N];
int f[N][N];int cmp(const int& a, const int& b) {return a < b;
}int dp() {for (int i = 1; i <= n; i++)b[i] = a[i];sort(b + 1, b + 1 + n, cmp);for (int i = 1; i <= n; i++) {int minv = 0x3f3f3f3f;for (int j = 1; j <= n; j++) {minv = min(minv, f[i-1][j]);f[i][j] = minv + abs(a[i] - b[j]);}}int ret = 0x3f3f3f3f;for (int i = 1; i <= n; i++)ret = min(ret, f[n][i]);return ret;
}int main() {cin >> n;for (int i = 1; i <= n; i++)scanf("%d", &a[i]);int ans = dp();reverse(a + 1, a + 1 + n);ans = min(ans, dp());cout << ans << endl;return 0;
}