题目:
给定长度为 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 代码:
- #include<iostream>
- #include<algorithm>
- #include<cstring>
- #include<cstdio>
- #include<cmath>
- using namespace std;
- typedef long long ll;
- const int maxn=2100;
- ll a[maxn],b[maxn];
- ll dp[maxn][maxn];
- int n;
- //dp[i][j] 代表的是前 i 个数字花费最小, 并且以 num[j] 结尾的最小花费
- // 由于数字的范围很大, 但是数字的数目比较少, 因此可以进行离散化, 把数字映射到区间上
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- scanf("%lld",&a[i]);
- b[i]=a[i];
- }
- sort(b+1,b+1+n);
- int m=unique(b+1,b+1+n)-b-1;
- memset(dp,0,sizeof(dp));
- for(int i=1;i<=n;i++)
- {
- ll tmp=dp[i-1][1];
- for(int j=1;j<=m;j++)
- {
- tmp=min(tmp,dp[i-1][j]);
- dp[i][j]=tmp+abs(a[i]-b[j]);
- }
- }
- ll ans=0x3f3f3f3f;
- for(int i=1;i<=m;i++)
- ans=min(ans,dp[n][i]);
- printf("%lld\n",ans);
- }
来源: http://www.bubuko.com/infodetail-3156218.html