AcWing 273 分级

题目大意

给定长度为 $N$ 的序列 $A$, 构造一个长度为 $N$ 的序列 $B$, 满足:

$B$ 非严格单调, 即 $B_1 \leq B_2 \leq \ldots \leq B_N$ 或 $B_1 \geq B_2 \geq \cdots \geq B_N$ 。
最小化$S=\sum_{i=1}^N\left|A_i-B_i\right|$

求出$S$

数据范围:

$1 \leq N \leq 2000$

$0\leq A_i \leq 10^6$

输入样例

7
1
3
2
4
5
3
9

输出样例

题解

从大到下和从小到大本质上就是一个镜像过程，做两遍即可。

这里做两遍也有一个小技巧，方便coding。即不选择做两遍，一次从小到大，一次从大到小，而是选择将原始的$A$反序，再做一遍。

重要结论

这道题需要推导出一个重要的结论

肯定存在在一个答案解，满足对于$\forall B_i, \exists A_j, \text{s.t. } B_i = A_j $

证明如下，

设$A’$ 为$A$的不降序排列，$B$为最优解对应的一种方案。则假设$\left[A’i, A’{i+1}\right]$中存在着$B_j, B_{j+1}, \cdots, B_k$，他们分别对应着$A_j, A_{j+1}, \cdots, A_{k}$, 记其$> A’_i$的个数为x个， $<A’$的个数为y个，分以下三种情况

$x>y$, 则说明${A_j}$，整体偏大，因此可以将${B_j}$整体往大了调，使得$\mathcal{max}{B_j} = A’_{i+1}$，若最大的增加了d，则优化了d(x-y)
$y<x$, 同理可得，往下了调，使得$\mathcal{min}{B_j} = A’_i$，优化了d(y-x)
$y=x$, 则不变

经过上述的优化之后，则最后会达成这个结论。

DP方程分析

则有了以上的结论，就可以对这个题分析得到${B}$一定会以其中一个$A_i$结尾，因此可以列出状态$f_{i,j}$表式前i个数中，以$A’j$结尾的最小代价。接下来考虑$f{i,j}$会从哪些方面转移得到，将其状态进行划分，则可以得到$B_{i-1}$必定为$A’1, A’_2, \cdots, A’{i-1}$中的一个，因此可以得到以下状态转移方程

\[f_{i,j} = \mathop{min}\limits_{1 \le k \le j} \left\{f_{i, k} \right \} + \left |A_i - A'_j \right|\]

这其中$\mathop{min}\limits_{1 \le k \le j}{f_{i,k}}$可以用类似前缀和的思想，每次遍历j的时候进行维护，减少一层循环，最后的时间复杂度为$O(n^2)$

代码

//
// Created by Leo on 2023/2/17.
//

#include <bits/stdc++.h>

using namespace std;

const int MaxN = 2050, INF = 0x7fffffff;
int A[MaxN], B[MaxN], N, f[MaxN][MaxN];

int solve() {
    copy(A, A+N, B);
    sort(B, B + N);
    // f[i, j] = min(f[i - 1, k])(1 <= k <= j) + |A[i] - B[j]|)
    memset(f, 0, sizeof(f));
    for (int i = 0; i < N; i++) {
       int minv = INF;
       for (int j = 0; j < N; j++) {
           minv = (i < 1) ? 0 : min(minv, f[i-1][j]);
           f[i][j] = minv + abs(A[i] - B[j]);
       }
    }
    int ans = INF;
    for ( int i = 0; i < N; i++) {
        ans = min(ans, f[N - 1][i]);
    }
    return ans;
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    int ans;
    ans = solve();
    reverse(A, A + N);
    ans = min(ans, solve());
    cout << ans << endl;
    return 0;
}

AcWing 273-分级题解报告

动态规则01

AcWing 273 分级

题目大意

题解

重要结论

DP方程分析

代码

CATALOG