当前位置: 首页 > news >正文

3 ACwing 273 Making the Grade 题解

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;
}
http://www.hskmm.com/?act=detail&tid=25018

相关文章:

  • 1 ACwing 271 Mr
  • 2 ACwing 272 LCIS 最长公共上升子序列 题解
  • 用 Haxe 实现英文数字验证码识别
  • 出题四
  • 7 2025 07 15 模拟赛题解
  • 使用 OCaml 实现验证码识别
  • 私有云大数据部署:从开发到生产(Docker、K8s、HDFS/Flink on K8s) - 详解
  • 差分约束模板
  • 17 LCA模拟赛1T2 剧院始于演员 题解
  • 3 2025 04 23 模拟赛总结
  • 14 收心赛3 T1 最长不降子序列 题解
  • 16 LCA模拟赛1T1 密码 题解
  • 吴恩达深度学习课程一:神经网络和深度学习 第二周:神经网络基础(一)
  • 阿里开源规则引擎QLExpress
  • QOJ7411 Bitwise Xor
  • 完整教程:SOC-ESP32S3部分:25-HTTP请求
  • 为什么要采用“接口 - 抽象类 - 实现类”这种三层结构? - 浪矢
  • 对外提供 AI 服务的风险:合规视角与 AI 安全围栏落地指南
  • VScode C/C++ 汉化 竞赛版 只需下载扩展 (超简单)
  • 网络安全工具与社区讨论月报
  • 机器人运动未来与人机交互研究
  • 欧拉路径 欧拉图 小记
  • OI 笑传 #16
  • cf296b
  • 第一次使用Ttpora
  • Apache反向代理
  • 原版 Sunshine+虚拟显示器实现熄屏串流
  • 2025国庆Day4
  • gis坐标计算
  • day17 课程()