原题链接https://www.acwing.com/problem/content/275/

题目描述

给定长度为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≤109 输入样例： 7 1 3 2 4 5 3 9 输出样例： 3

题解

本题需要推导出一个性质：要满足上述要求，则序列B中的每一个数必须在A序列中出现过 则题目要求就变成在序列A中找到N个单调的数(可以相同，重复，不一定是找A中所有的数)，使得满足题目要求。 状态表示： f[i][j] 代表所有给A[1] ~ A[i]分配好了值且最后一个B[i] = A’[j]的方案的集合； f[i][j] 的值是集合中所有方案的最小值； 状态计算： 依据倒数第二个数分配的是哪个A’[i]将f[i][j]所代表的集合划分成j个不重不漏的子集： 倒数第二个数选取的是A’[1]的所有方案的结合，最小值是 f[i - 1][1] + abs(A[i] - A’[j]); 倒数第二个数选取的是A’[2]的所有方案的结合，最小值是 f[i - 1][2] + abs(A[i] - A’[j]); … 倒数第二个数选取的是A’[j]的所有方案的结合，最小值是 f[i - 1][j] + abs(A[i] - A’[j]); f[i][j]在所有子集的最小值中取min即可。 最终答案需要遍历最后一个数的所有取值，然后取min即可。

#include "iostream" #include "algorithm" #include "cmath" using namespace std; const int N = 2010, INF = 0x3f3f3f3f; int n; int a[N], b[N]; int f[N][N]; int dp(){ for(int i = 1; i <= n; i++) b[i] = a[i]; sort(b+1,b+n+1); /*for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ //枚举B最后一个状态 int minv = INF; for(int k = 1; k <= j; k++){ //枚举B倒数第二个数的状态 minv = min(minv, f[i-1][k]); } f[i][j] = minv+abs(a[i]-b[j]); } }*/ for(int i = 1; i <= n; i++){ int minv = INF; for (int j = 1; j <= n; j ++ ) { minv = min(minv, f[i - 1][j]); f[i][j] = minv + abs(a[i] - b[j]); } } int res = INF; for (int i = 1; i <= n; i ++ ) res = min(res, f[n][i]); return res; } int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); int res = dp(); reverse(a+1,a+n+1); res = min(res, dp()); printf("%d\n", res); return 0; }