题目：
给定长度为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≤20001≤|Ai|≤10^9
输入样例：
7
1
3
2
4
5
3
9
输出样例：
3解题报告：这是一道dp的题目，咱们首先要保证的就是这个b序列应该是非严格单调的，要求他的差值的绝对值之和最小，所以咱们就要尽可能地满足最长上升子序列（维护最小地花费），先把a数组存进另一个数组里，进行离散化处理，别的题解说的是数据的范围过大且数目较少，但是我没有很理解这点，维护地dp数组，dp[i][j]代表地就是前i个数以b[j]作为结束地最小花费，这里的貌似只需要维护递增的就可以，不需要去处理递减的情况ac代码：
1 #include<iostream>
2 #include<algorithm>
3 #include<cstring>
4 #include<cstdio>
5 #include<cmath>
6 using namespace std;
7 typedef
long long ll;
8
9 const int maxn=
2100;
10 ll a[maxn],b[maxn];
11 ll dp[maxn][maxn];
12 int n;
13 //dp[i][j] 代表的是前i个数字花费最小，并且以num[j]结尾的最小花费
14 //由于数字的范围很大，但是数字的数目比较少，因此可以进行离散化，把数字映射到区间上
15 int main()
16 {
17 scanf(
"%d",&
n);
18 for(
int i=
1;i<=n;i++
)
19 {
20 scanf(
"%lld",&
a[i]);
21 b[i]=
a[i];
22 }
23 sort(b+
1,b+
1+
n);
24 int m=unique(b+
1,b+
1+n)-b-
1;
25 memset(dp,
0,
sizeof(dp));
26 for(
int i=
1;i<=n;i++
)
27 {
28 ll tmp=dp[i-
1][
1];
29 for(
int j=
1;j<=m;j++
)
30 {
31 tmp=min(tmp,dp[i-
1][j]);
32 dp[i][j]=tmp+abs(a[i]-
b[j]);
33 }
34 }
35 ll ans=
0x3f3f3f3f;
36 for(
int i=
1;i<=m;i++
)
37 ans=
min(ans,dp[n][i]);
38 printf(
"%lld\n",ans);
39
40
41 }
