ACwing 273 Making the Grade
题面
给定长度为 \(N\) 的序列 \(A\) ，构造一个长度为 \(N\) 的序列 \(B\) ，满足
- \(B\) 非严格单调
- \(S = \sum_{i = 1}^N |A_i - B_i|\) 最小
求出最小值 \(S\)
\(1 \le N \le 2000\)
\(0 \le A_i \le 10^6\)
题解
先证明一个引理：\(B\) 中的所有数都在 \(A\) 中出现过
我们利用数学归纳法进行证明
首先对于 \(k + 1 = 1\) 的情况，显然成立
对于 \(k + 1 > 1\) 的情况
-
若 \(A_{k + 1} \ge B_k\) 我们取 \(B_{k + 1} = A_{k + 1}\) 即可
-
否则，要么 \(B_{k + 1} = B_k\) ，要么存在 \(x\) 使得 \(B_j...B_{k + 1} = x\)
设 \(mid\) 为 \(A_j...A_{k + 1}\) 的中位数，根据货仓选址一题，如果 \(mid \ge B_{j - 1}\) \(x = mid\) ，否则 \(x = B_{j - 1}\)
对于以上情况，涵盖了最优解的同时也保证了 \(B\) 中的所有数都在 \(A\) 中出现过
所以我们就证明了引理
因为这道题的限制为序列递增，所以我们需要知道序列中数的大小关系
设 \(f(i,j)\) 表示考虑前 \(i\) 个数 \(B_i = j\) 的情况下的最小代价，初始 \(f(0,i) = 0\) ，目标状态为 \(\min \{f(n,i)\}\)
转移：\(f(i,j) = \min_{0 \le k \le j} \{f(i - 1, k) + |A_i - j|\}\)
这个候选集合也是只增不减的，可以用一个变量维护，将 \(A\) 离散化后，时间复杂度 \(O(N^2)\)
code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;const int N = 2e3 + 10;
const int INF = 2147483647;int n;
int a[N], f[N][N];
int num[N];int work () {int res = INF;memset (f, 0x3f, sizeof f);for (int i = 1; i <= n; i++) f[0][i] = 0;for (int i = 1; i <= n; i++) {int mn = INF;for (int j = 1; j <= n; j++) {mn = min (mn, f[i - 1][j]);f[i][j] = mn + abs (a[i] - num[j]);}}for (int i = 1; i <= n; i++) {res = min (res, f[n][i]);}return res;
}int main () {cin >> n;for (int i = 1; i <= n; i ++) {cin >> a[i];num[i] = a[i];}//num[i] 表示排名第 i 个的 a_isort (num + 1, num + 1 + n);int ans = work ();//反转后，相当于在求递减的 breverse (a + 1, a + 1 + n);ans = min (ans, work ());cout << ans << endl;return 0;
}