P2893 [USACO08FEB] Making the Grade G 题目分析
分析题目性质
不难解析出题目中的序列 \(B\) 有“单调不下降”和“单调不上升”两种情况，不难想到分两种情况讨论答案即可。
有一个性质：
在满足答案最小化的情况，一定存在一种方案使得 \(B\) 中的数字一定在 \(A\) 中。
不难证明其方案是不劣于不在 \(A\) 中的数的。
考虑李煜东的证明：
考虑用数学归纳法证明。
命题对 \(n=1\) 显然成立。
设这个性质对于 \(n=k-1\) 成立，此时构造出的序列为 \(B_1,\dots,B_{k-1}.\)
当 \(n = k\) 时，将有以下的两种情况：
- \(B_{k-1}\leq A_k\)，则令 \(B_k=A_k\) 命题成立且满足单调性。
- \(B_{k-1}>A_k\)，则有：
- 存在一段连续相同的 \(B\)，即存在一个 \(j<k\) 使得 \(B_j=B_{j+1}=\dots=B_k=v\)，有以下的构造方法：
- 设 \(A_j,\dots,A_k\) 的中位数为 \(mid\)，若 \(mid\geq B_{j-1}\) 则有 \(v=mid\)，否则应该有 \(v=B_{j-1}.\)
- 否则，直接令 \(B_k=B_{k-1}.\)
思路
综上，我们考虑：完成前 \(i\) 个数的构造时，当前前 \(i\) 个计入答案的最小值，也就是把 \(dp\) 的阶段设为已经处理完的前缀序列的长度，转移的时候，我们也要确定 \(B_i\) 和 \(B_{i-1}\) 的值以此来确定单调性。
我们思考了一下，这不就是 \(\text{LIS}\) 问题吗？直接设 \(f_i\) 表示完成前 \(i\) 个数后，并且 \(B_i=A_i\) 时，答案的最小值。
转移是简单的：
\[f_i=\min_{0\leq j<i,A_j\leq A_i} f_j+cost(j+1,i-1) \]其中的 \(cost(j+1,i-1)\) 表示构造 \(B_x\) 的区间 \(x\in[j+1,i-1]\) 满足条件时，答案的最小值。
不难完成对 \(cost(j+1,i-1)\) 的计算，即只需要计算什么时候前面与 \(A_j\) 相同，后面与 \(A_i\) 相同，使答案最小。
扫一遍即可，总时间复杂度 \(\mathcal{O}(n^3)\)，无法通过本题。
考虑状态优化，使的状态和转移的综合在一起最小。
具体的，设 \(f_{i,j}\) 表示已经处理完前 \(i\) 个数后 \(B_i=j\) 时，答案的最小值。
初始化肯定是全为 \(0\) 的（考虑到转移有对应的操作）。
因为状态已经是二维的了，我们要使转移是 \(\mathcal{O}(n)\) 以下的。
怎么想呢？
朴素的，直接枚举上一个数 \(B_{i-1}\) 是什么，我们想到了以下转移：
\[f_{i,j}=\min_{0\leq k\leq j} f_{i-1,k}+|A_i-j| \]考虑跟 \(\text{LCIS}\) 一样的优化：即把重复的取 \(\min\) 提取出来，存入一个变量。
决策集合只增不减，因此转移是 \(\mathcal{O}(1)\) 的。
而根据性质，\(j\) 可以用离散化解决，也可以设为 \(A_j\)。
因此，总时间复杂度 \(\mathcal{O}(n^2)\) 的。
注意，因为要求单调，所以一定要对离散过的 \(A\) 进行排序，否则就有可能不单调。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stdlib.h>
#include <cmath>
#define int long long
#define N 2005
using namespace std;
int n,a[N],ans = 2e9,f[N][N],num[N];
signed main(){
cin >> n;
for (int i = 1;i <= n;i ++) cin >> a[i],num[i] = a[i];
stable_sort(num + 1,num + 1 + n);
memset(f,0,sizeof f);
for (int i = 1;i <= n;i ++) {
int mn = 2e9;
for (int j = 1;j <= n;j ++) {
mn = min(mn,f[i - 1][j]);
f[i][j] = mn + abs(num[j] - a[i]);
}
}
for (int j = 1;j <= n;j ++) ans = min(ans,f[n][j]);
reverse(num + 1,num + 1 + n);
memset(f,0,sizeof f);
for (int i = 1;i <= n;i ++) {
int mn = 2e9;
for (int j = 1;j <= n;j ++) {
mn = min(mn,f[i - 1][j]);
f[i][j] = mn + abs(num[j] - a[i]);
}
}
for (int j = 1;j <= n;j ++) ans = min(ans,f[n][j]);
cout << ans;
return 0;
}