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

线性dp,优化记录,273. 分级

273. 分级

273. 分级 - AcWing题库

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

  1. B 非严格单调,即 B1≤B2≤…≤BN 或 B1≥B2≥…≥BN。
  2. 最小化 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&#xff0c;构造一个长度为 N 的序列 B&#xff0c;满足&#xff1a; B 非严格单调&#xff0c;即 B1≤B2≤…≤BN 或 B1≥B2≥…≥BN。最小化 S∑Ni1|Ai−Bi|。 只需要求出这个最小值 S。 输入格式 第一行包含一…...

JWT 安全及案例实战

文章目录 一、JWT (json web token)安全1. Cookie&#xff08;放在浏览器&#xff09;2. Session&#xff08;放在服务器&#xff09;3. Token4. JWT (json web token)4.1 头部4.1.1 alg4.1.2 typ 4.2 payload4.3 签名4.4 通信流程 5. 防御措施 二、漏洞实例&#xff08;webgoa…...

Vue2+Vue3

文章目录 Vue快速上手Vue是什么第一个Vue程序插值表达式Vue核心特性&#xff1a;响应式 Vue指令v-htmlv-show 与 v-ifv-else 与 v-else-ifv-onv-bindv-forv-model指令修饰符 计算属性watch侦听器&#xff08;监视器&#xff09;watch——简写watch——完整写法 Vue生命周期 和 …...

华为云云耀云服务器L实例评测|redis漏洞回顾 MySQL数据安全解决 搭建主从集群MySQL 相关设置

前言 最近华为云云耀云服务器L实例上新&#xff0c;也搞了一台来玩&#xff0c;期间遇到过MySQL数据库被攻击的情况&#xff0c;数据丢失&#xff0c;还好我有几份备份&#xff0c;没有造成太大的损失&#xff1b;后来有发现Redis数据库被攻击的情况&#xff0c;加入了redis密…...

【C++】详解std::thread

2023年9月10日&#xff0c;周日下午开始 2023年9月10日&#xff0c;周日晚上23:35完成 虽然这篇博客我今天花了很多时间去写&#xff0c;但是我对std::thread有了一个完整的认识 不过有些内容还没完善&#xff0c;以后有空再更新.... 目录 头文件类的成员类型方法(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介绍&#xff1a;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中实现生成二维码功能(代码示例)

完整示例&#xff1a; <template><view><view class"titleBar">执法检查“通行码”信息</view><view class"twoCode"><canvas canvas-id"qrcode"></canvas></view></view> </templat…...

深度解剖数据在栈中的应用

> 作者简介&#xff1a;დ旧言~&#xff0c;目前大一&#xff0c;现在学习Java&#xff0c;c&#xff0c;c&#xff0c;Python等 > 座右铭&#xff1a;松树千年终是朽&#xff0c;槿花一日自为荣。 > 望小伙伴们点赞&#x1f44d;收藏✨加关注哟&#x1f495;&#x1…...

Android10 SystemUI系列 需求定制(一)状态栏控制中心默认tile定制属性适配

一、前言 SystemUI 所包含的界面和模块比较多,这一节主要分享一下控制中心默认tile 列表的实现,通过配置可以实现 下拉状态栏,控制中心默认的tile显示 二、准备工作 按照惯例先找一下控制中心的代码,主要在下面这个路径下 frameworks/base/packages/SystemUI/src/com/andr…...

【微信小程序】文章设置

设置基本字体样式&#xff1a;行高、首行缩进 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…...

程序员在线周刊(冒泡算法篇)

大家好&#xff0c;欢迎来到程序员在线周刊&#xff01;本期我们将深入探讨一种经典的排序算法——冒泡算法&#xff0c;并附上具体的代码实现。 目录 简介代码原理广告广告1广告2广告3 简介 冒泡算法是一种简单但效率较低的排序算法&#xff0c;它的原理非常直观&#xff1a…...

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.引入 官网地址&#xff1a; https://layui.gitee.io/v2/ 引入&#xff08;在官网下载&#xff0c;&#xff09;jquery-1.7.2.min.js,layui/layui.js **<link href"js/layui/css/layui.css" rel"stylesh…...

OPPO哲库事件 “ 始末 ” ! 集体打哑谜?

1►OPPO哲库解散 2019 年&#xff0c;美国商务部以“科技网络安全”为由&#xff0c;将华为公司及其70家附属公司列入出口管制“实体名单”。与此同时&#xff0c;OPPO 创始人兼 CEO陈明永对外宣布&#xff0c;公司将为未来三年内投入 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&#xff09;什么是 Microsoft Excel&#xff1f; Microsoft Excel 是一个电子电子表格应用程序&#xff0c;使用户可以使用按行和列细分的电子表格系统&#xff0c;使用公式存储&#xff0c;组织&#xff0c;计算和处理数据。 它还提供了使用外部数据库进行分析&#xff0c;…...

ros2学习笔记:shell环境变量脚本setup.bash[-z][-n][-f]参数作用

-n作用 [ -n 字符串 ] or [ 字符串 ] 字符串的长度为非零&#xff08;有内容&#xff09;则为真。加-n与不加-n结果相同。 -z作用 [ -z 字符串 ] 字符串的长度为零则为真。 字符串为空即NULL时为真&#xff0c;与上面的-n相反。 -f作用 [ -f FILE ] 如果 FILE 存在且是一…...

xss渗透(跨站脚本攻击)

一、什么是XSS? XSS全称是Cross Site Scripting即跨站脚本&#xff0c;当目标网站目标用户浏览器渲染HTML文档的过程中&#xff0c;出现了不被预期的脚本指令并执行时&#xff0c;XSS就发生了。 这里我们主要注意四点&#xff1a; 1、目标网站目标用户&#xff1b; 2、浏览…...

9参数化重采样时频变换,基于MATLAB平台,程序已调通,可直接替换数据进行分析。

参数化重采样时频变换&#xff0c;基于MATLAB平台&#xff0c;程序已调通&#xff0c;可直接替换数据进行分析。 9matlab参数化重采样时频变换 (xiaohongshu.com)...

逆向工程必备:用aardio和Sunny中间件抓取手机App封包的3种实战姿势

逆向工程实战&#xff1a;aardio与Sunny中间件的移动端封包拦截艺术 在移动应用安全研究领域&#xff0c;封包拦截与分析是理解应用通信逻辑的关键入口。不同于传统的PC端抓包&#xff0c;移动环境面临着证书绑定、代理检测等更复杂的防御机制。aardio配合Sunny中间件构建的轻量…...

3种激活方案:解决IDM弹窗问题的开源工具应用指南

3种激活方案&#xff1a;解决IDM弹窗问题的开源工具应用指南 【免费下载链接】IDM-Activation-Script IDM Activation & Trail Reset Script 项目地址: https://gitcode.com/gh_mirrors/id/IDM-Activation-Script 一、问题溯源&#xff1a;解析IDM激活弹窗的技术本质…...

华为MateBook D14安装Ubuntu16避坑指南:WiFi/蓝牙/触控板驱动一键搞定

华为MateBook D14安装Ubuntu 16.04驱动优化全攻略 华为MateBook D14作为一款高性价比轻薄本&#xff0c;在安装Ubuntu 16.04时可能会遇到WiFi、蓝牙和触控板驱动不兼容的问题。这主要源于硬件迭代速度远超Linux内核更新周期——你的笔记本搭载了新一代无线网卡和输入设备&#…...

DXVK性能优化:让老旧系统重获新生的完美方案

DXVK性能优化&#xff1a;让老旧系统重获新生的完美方案 【免费下载链接】dxvk Vulkan-based implementation of D3D9, D3D10 and D3D11 for Linux / Wine 项目地址: https://gitcode.com/gh_mirrors/dx/dxvk 为什么老旧电脑运行新程序总是卡顿&#xff1f;DXVK如何解决…...

从零开始:用QGIS和PostgreSQL构建交通路线空间数据库(含Python脚本自动化技巧)

从零开始&#xff1a;用QGIS和PostgreSQL构建交通路线空间数据库&#xff08;含Python脚本自动化技巧&#xff09; 在交通规划与智慧城市建设的浪潮中&#xff0c;空间数据的高效管理成为技术团队的核心挑战。传统文件存储方式难以应对大规模交通网络数据的实时查询与分析需求&…...

Dify私有化部署实战:如何在企业内网快速搭建AI开发平台(含Docker镜像打包技巧)

Dify私有化部署实战&#xff1a;企业内网AI开发平台搭建全攻略 1. 企业内网部署Dify的核心价值与挑战 在数字化转型浪潮中&#xff0c;越来越多的企业开始将AI能力纳入核心业务系统。Dify作为开源的大语言模型应用开发平台&#xff0c;其私有化部署方案尤其适合对数据安全有严…...

效率提升秘籍:用快马AI自动生成六花直装更新页面,节省开发时间

作为一名经常需要维护应用更新页面的开发者&#xff0c;我深刻体会到手动编写更新日志的繁琐。每次版本迭代&#xff0c;从整理更新内容到排版发布&#xff0c;往往要耗费大量时间。最近尝试用InsCode(快马)平台的AI功能自动生成更新页面&#xff0c;效率提升非常明显。 传统更…...

路侧3D检测翻车实录:Rope3D数据集标签里的航向角坑,我是怎么填上的

路侧3D检测实战&#xff1a;Rope3D数据集航向角问题的深度解析与修复方案 当你在深夜盯着屏幕上那些"反向行驶"的虚拟车辆时&#xff0c;那种荒诞感会让人瞬间清醒。这不是科幻场景&#xff0c;而是我在使用Rope3D数据集进行路侧3D目标检测时遇到的真实困境——车辆航…...

【仿真】Carla跨平台部署指南:从零到一,附ROS2与Autoware.auto连接实战

1. Carla仿真平台概述 Carla是一款开源的自动驾驶仿真平台&#xff0c;基于虚幻引擎构建&#xff0c;能够提供高度逼真的城市环境和交通场景。我第一次接触Carla是在2018年&#xff0c;当时它还处于早期开发阶段&#xff0c;但已经展现出惊人的潜力。经过多年发展&#xff0c;现…...

利用快马平台快速生成PyTorch图像分类原型,十分钟验证模型思路

最近在尝试用PyTorch做图像分类的原型验证时&#xff0c;发现从零开始搭建环境、写基础代码特别耗时。后来尝试用InsCode(快马)平台生成项目模板&#xff0c;十分钟就完成了模型验证。这里分享下用PyTorch快速构建MNIST分类器的关键步骤和踩坑经验。 数据准备环节 平台生成的代…...