线性dp,优化记录,273. 分级
273. 分级
273. 分级 - AcWing题库
给定长度为 N 的序列 A,构造一个长度为 N 的序列 B,满足:
- B 非严格单调,即 B1≤B2≤…≤BN 或 B1≥B2≥…≥BN。
- 最小化 S=∑Ni=1|Ai−Bi|。
只需要求出这个最小值 S。
输入格式
第一行包含一个整数 N。
接下来 N 行,每行包含一个整数 Ai。
输出格式
输出一个整数,表示最小 S 值。
数据范围
1≤N≤2000
0≤Ai≤106
输入样例:
7
1
3
2
4
5
3
9
输出样例:
3
解析
题目非常好,但我还没吃透,理解的不够深,解析先不写,现附上acwing的题解,等完全掌握后再写解析
AcWing 273. 分级 - AcWing
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>using namespace std;
typedef long long LL;
const int N = 2e3 + 5;
int n;
int a[N], b[N];
int f[N][N];int cmp(const int& a, const int& b) {return a < b;
}int dp() {for (int i = 1; i <= n; i++)b[i] = a[i];sort(b + 1, b + 1 + n, cmp);for (int i = 1; i <= n; i++) {int minv = 0x3f3f3f3f;for (int j = 1; j <= n; j++) {minv = min(minv, f[i-1][j]);f[i][j] = minv + abs(a[i] - b[j]);}}int ret = 0x3f3f3f3f;for (int i = 1; i <= n; i++)ret = min(ret, f[n][i]);return ret;
}int main() {cin >> n;for (int i = 1; i <= n; i++)scanf("%d", &a[i]);int ans = dp();reverse(a + 1, a + 1 + n);ans = min(ans, dp());cout << ans << endl;return 0;
}
相关文章:
线性dp,优化记录,273. 分级
273. 分级 273. 分级 - AcWing题库 给定长度为 N 的序列 A,构造一个长度为 N 的序列 B,满足: B 非严格单调,即 B1≤B2≤…≤BN 或 B1≥B2≥…≥BN。最小化 S∑Ni1|Ai−Bi|。 只需要求出这个最小值 S。 输入格式 第一行包含一…...
JWT 安全及案例实战
文章目录 一、JWT (json web token)安全1. Cookie(放在浏览器)2. Session(放在服务器)3. Token4. JWT (json web token)4.1 头部4.1.1 alg4.1.2 typ 4.2 payload4.3 签名4.4 通信流程 5. 防御措施 二、漏洞实例(webgoa…...
Vue2+Vue3
文章目录 Vue快速上手Vue是什么第一个Vue程序插值表达式Vue核心特性:响应式 Vue指令v-htmlv-show 与 v-ifv-else 与 v-else-ifv-onv-bindv-forv-model指令修饰符 计算属性watch侦听器(监视器)watch——简写watch——完整写法 Vue生命周期 和 …...
华为云云耀云服务器L实例评测|redis漏洞回顾 MySQL数据安全解决 搭建主从集群MySQL 相关设置
前言 最近华为云云耀云服务器L实例上新,也搞了一台来玩,期间遇到过MySQL数据库被攻击的情况,数据丢失,还好我有几份备份,没有造成太大的损失;后来有发现Redis数据库被攻击的情况,加入了redis密…...
【C++】详解std::thread
2023年9月10日,周日下午开始 2023年9月10日,周日晚上23:35完成 虽然这篇博客我今天花了很多时间去写,但是我对std::thread有了一个完整的认识 不过有些内容还没完善,以后有空再更新.... 目录 头文件类的成员类型方法(construc…...
Apache HTTPD 漏洞复现
文章目录 Apache HTTPD 漏洞复现1. Apache HTTPD 多后缀解析漏洞1.1 漏洞描述1.2 漏洞复现1.3 漏洞利用1.4 获取GetShell1.5 漏洞防御 2. Apache HTTPD 换行解析漏洞-CVE-2017-157152.1 漏洞描述2.2 漏洞复现2.3 漏洞利用2.4 修复建议 3. Apache HTTP Server_2.4.49 路径遍历和…...
【C++从入门到精通】第2篇:C++基础知识(中)
文章目录 2.1 iostream介绍:cout、cin和endl2.1.1 输入/输出库2.1.2 std::cout2.1.3 std::endl2.1.4 std::cout是缓冲的2.1.5 std::endl与\n2.1.6 std::cin2.1.7 总结2.1.8 练习时间 2.2 未初始化的变量和未定义的行为2.2.1 未初始化的变量2.2.2 未定义行为2.2.3 明…...
【RuoYi移动端】uni-app中实现生成二维码功能(代码示例)
完整示例: <template><view><view class"titleBar">执法检查“通行码”信息</view><view class"twoCode"><canvas canvas-id"qrcode"></canvas></view></view> </templat…...
深度解剖数据在栈中的应用
> 作者简介:დ旧言~,目前大一,现在学习Java,c,c,Python等 > 座右铭:松树千年终是朽,槿花一日自为荣。 > 望小伙伴们点赞👍收藏✨加关注哟💕…...
Android10 SystemUI系列 需求定制(一)状态栏控制中心默认tile定制属性适配
一、前言 SystemUI 所包含的界面和模块比较多,这一节主要分享一下控制中心默认tile 列表的实现,通过配置可以实现 下拉状态栏,控制中心默认的tile显示 二、准备工作 按照惯例先找一下控制中心的代码,主要在下面这个路径下 frameworks/base/packages/SystemUI/src/com/andr…...
【微信小程序】文章设置
设置基本字体样式:行高、首行缩进 font-size: 32rpx;line-height: 1.6em;text-indent: 2em;padding: 20rpx 0;border-bottom: 1px dashed var(--themColor); 两端对齐 text-align: justify; css文字两行或者几行显示省略号 css文字两行或者几行显示省略号_css…...
程序员在线周刊(冒泡算法篇)
大家好,欢迎来到程序员在线周刊!本期我们将深入探讨一种经典的排序算法——冒泡算法,并附上具体的代码实现。 目录 简介代码原理广告广告1广告2广告3 简介 冒泡算法是一种简单但效率较低的排序算法,它的原理非常直观:…...
string
目录 六、STL简介 (一)什么是STL (二)STL的版本 (三)STL六大组件 七、string (一)标准库中的string 1、string类 2、string常用的接口 1)string类对象的常见构造 2)string类对象的容量操作 3)string类对象的访问及遍历操作 4)string类对象的修改操作 5)string类非成…...
html的日期选择插件
1.效果 2.文档 https://layui.gitee.io/v2/docs/ 3.引入 官网地址: https://layui.gitee.io/v2/ 引入(在官网下载,)jquery-1.7.2.min.js,layui/layui.js **<link href"js/layui/css/layui.css" rel"stylesh…...
OPPO哲库事件 “ 始末 ” ! 集体打哑谜?
1►OPPO哲库解散 2019 年,美国商务部以“科技网络安全”为由,将华为公司及其70家附属公司列入出口管制“实体名单”。与此同时,OPPO 创始人兼 CEO陈明永对外宣布,公司将为未来三年内投入 500 亿元用于前沿技术和深水区技术的探索…...
数据聚类分析
K均值 1.1 数据来源(随机生成) import matplotlib.pyplot as plt from sklearn.datasets import make_blobsX, y make_blobs(n_samples150,n_features2,centers3,cluster_std0.5,shuffleTrue,random_state0) # plt.scatter(X[:, 0], X[:, 1], cwhite, markero, edgecolorsbl…...
前 40 个 Microsoft Excel 面试问题答案
1)什么是 Microsoft Excel? Microsoft Excel 是一个电子电子表格应用程序,使用户可以使用按行和列细分的电子表格系统,使用公式存储,组织,计算和处理数据。 它还提供了使用外部数据库进行分析,…...
ros2学习笔记:shell环境变量脚本setup.bash[-z][-n][-f]参数作用
-n作用 [ -n 字符串 ] or [ 字符串 ] 字符串的长度为非零(有内容)则为真。加-n与不加-n结果相同。 -z作用 [ -z 字符串 ] 字符串的长度为零则为真。 字符串为空即NULL时为真,与上面的-n相反。 -f作用 [ -f FILE ] 如果 FILE 存在且是一…...
xss渗透(跨站脚本攻击)
一、什么是XSS? XSS全称是Cross Site Scripting即跨站脚本,当目标网站目标用户浏览器渲染HTML文档的过程中,出现了不被预期的脚本指令并执行时,XSS就发生了。 这里我们主要注意四点: 1、目标网站目标用户; 2、浏览…...
9参数化重采样时频变换,基于MATLAB平台,程序已调通,可直接替换数据进行分析。
参数化重采样时频变换,基于MATLAB平台,程序已调通,可直接替换数据进行分析。 9matlab参数化重采样时频变换 (xiaohongshu.com)...
超越单一工具:在快马平台探索多模型ai辅助开发的全新工作流
在开发过程中,AI辅助工具已经逐渐成为提升效率的利器。最近我在尝试使用InsCode(快马)平台时,发现它提供的多模型AI辅助开发能力,远比单一工具更加强大和灵活。下面分享一个我实践的综合示例项目,展示如何利用平台的多模型能力优化…...
降重不靠删,降AI不靠装——百考通用语义重构守住你的原创观点
在2026年的高校毕业季,一种新型的不公正在悄然制度化: 不是抄袭者被放过,而是原创者被怀疑; 不是敷衍者被批评,而是严谨者被标记; 不是懒惰者被警告,而是认真写了一篇好论文的人,被迫…...
3步搞定Google Drive受保护PDF:高效下载完整指南
3步搞定Google Drive受保护PDF:高效下载完整指南 【免费下载链接】Google-Drive-PDF-Downloader 项目地址: https://gitcode.com/gh_mirrors/go/Google-Drive-PDF-Downloader 你是否曾遇到过这样的情况?在Google Drive中找到一个急需的技术文档或…...
嵌入式 数据结构 线性表 学习笔记
线性表线性结构的特点是:1、存在唯一的一个被称作“第一个”的数据元素2、存在唯一的一个被称作“最后一个”的数据元素3、除第一个之外,集合中的每个元素均只有一个前驱4、除最后一个以外,集合中的每个数据元素均只有一个后继顺序表示和实现…...
3步释放20GB空间:给Android用户的系统减负指南
3步释放20GB空间:给Android用户的系统减负指南 【免费下载链接】universal-android-debloater Cross-platform GUI written in Rust using ADB to debloat non-rooted android devices. Improve your privacy, the security and battery life of your device. 项目…...
别再手动折腾了!用Docker一键部署Oracle 11g开发环境(附阿里云镜像地址)
告别繁琐配置:Docker容器化Oracle 11g开发环境实战指南 每当新项目需要搭建Oracle开发环境时,开发者们总会面临相同的困境——数小时的安装配置、复杂的系统依赖、难以复现的环境问题。传统安装方式不仅消耗宝贵时间,更可能因系统差异导致团…...
路侧3D检测翻车实录:Rope3D数据集标签里的航向角坑,我是怎么填上的
路侧3D检测实战:Rope3D数据集航向角问题的深度解析与修复方案 当你在深夜盯着屏幕上那些"反向行驶"的虚拟车辆时,那种荒诞感会让人瞬间清醒。这不是科幻场景,而是我在使用Rope3D数据集进行路侧3D目标检测时遇到的真实困境——车辆航…...
如何5分钟构建专业级黑苹果EFI?OpCore Simplify让复杂配置一键搞定
如何5分钟构建专业级黑苹果EFI?OpCore Simplify让复杂配置一键搞定 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 副标题:告别…...
Qwen3.5-4B-Claude-Opus部署教程:模型路径软链失效时的容错加载机制
Qwen3.5-4B-Claude-Opus部署教程:模型路径软链失效时的容错加载机制 1. 模型概述 Qwen3.5-4B-Claude-4.6-Opus-Reasoning-Distilled-GGUF是基于Qwen3.5-4B的推理蒸馏模型,特别强化了结构化分析、分步骤回答以及代码与逻辑类问题的处理能力。该版本以GG…...
2025年开源工具jable-download:视频下载工具高效解决方案
2025年开源工具jable-download:视频下载工具高效解决方案 【免费下载链接】jable-download 方便下载jable的小工具 项目地址: https://gitcode.com/gh_mirrors/ja/jable-download 在数字化内容消费日益增长的今天,视频资源的获取与保存成为许多用…...
