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

AtCoder Regular Contest 126 D题题解

思路

首先我们看看假设选中 mmm 个数后的答案。

我们首先现将 mmm 个数移动到一起,在将他们重新排序。

我们知道,mmm 个数移在一起时,当位于中间的那个数不动时交换次数最少,于是可以列出式子(cic_ici 是点 iii 的位置):

∑i=1m∣cmid+mid−ci+i∣\sum_{i = 1}^m |c_{mid} + mid - c_i + i| i=1mcmid+midci+i

我们可以将上面的式子改成如下形式:

−2m∗mid+m%2∗cmid+∑i=1mci−1i<=mid-\dfrac{2}{m}*mid + m \% 2 * c_{mid} + \sum_{i = 1}^m c_i^{-1^{i <=mid}} m2mid+m%2cmid+i=1mci1i<=mid

此时我们就可以用壮压DP来做了。

我们首先枚举每个数,在枚举选上这个数后的情况,在DP的过程中计算出下面的式子的求和公式里面的值,前面的为常数,并且在加上逆序对个数就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, mid, a[205], f[205][1 << 18], INF = 1e9;
int solve(int state, int i) {int sum = 0, t = 0, t1 = 0;//t是目前选了多少个数,t1选了的树中比这个数要小的数。for (int j = 0; j < m; j++) {if (state & (1 << j))t++;if (a[i] - 1 == j)t1 = t;}return i * (t <= mid ? -1 : 1) + i * (m & 1) * (mid == t) + (t - t1);//此时的i就是c值,于是我们把他带进去式子就可以了。
}
int main() {scanf("%d%d", &n, &m), mid = (m + 1) / 2;for (int i = 1; i <= n; i++) scanf("%d", &a[i]);memset(f, 36, sizeof(f));for (int i = 0; i <= n; i++) f[i][0] = 0;for (int i = 1; i <= n; i++)for (int j = 0; j < 1 << m; j++)f[i][j] = min(j & (1 << (a[i] - 1)) ? f[i - 1][j ^ (1 << (a[i] - 1))] + solve(j, i) : INF, f[i - 1][j]);printf("%d", f[n][(1 << m) - 1] - m / 2 * mid);return 0;
}

相关文章:

AtCoder Regular Contest 126 D题题解

思路 首先我们看看假设选中 mmm 个数后的答案。 我们首先现将 mmm 个数移动到一起&#xff0c;在将他们重新排序。 我们知道&#xff0c;mmm 个数移在一起时&#xff0c;当位于中间的那个数不动时交换次数最少&#xff0c;于是可以列出式子&#xff08;cic_ici​ 是点 iii 的…...

Android R WiFi热点流程浅析

Android R WiFi热点流程浅析 Android上的WiFi SoftAp功能是用户常用的功能之一&#xff0c;它能让我们分享手机的网络给其他设备使用。 那Android系统是如何实现SoftAp的呢&#xff0c;这里在FWK层面做一个简要的流程分析&#xff0c;供自己记录和大家参考。 以Android R版本为…...

【C++进阶】二、多态详解(总)

目录 一、多态的概念 二、多态的定义及实现 2.1 多态的构成条件 2.2 虚函数 2.3 虚函数的重写 2.4 虚函数重写的两个例外 2.4.1 协变 2.4.2 析构函数的重写 2.5 C11 override 和 final 2.5.1 final 2.5.2 override 2.6 重载、覆盖(重写)、隐藏(重定义)的对比 三、…...

node-sass@4.14.1 包含风险, 如何升级依赖至 dart-sass

文章目录需求我上网都查到了哪些信息在 github 看到了 node-sass 依赖的最新版本的列表&#xff1a;关于方案2的失败不同版本的 nodejs 和 node-sass依赖的**适配关系**从何得知替代方案——dart-sass如何安装 dart sass&#xff1f;需求 在做一个基于Node、React的前端项目&a…...

DataWhale 大数据处理技术组队学习task2

三、Hadoop分布式文件系统 1. 产生背景 数据量越来越大&#xff0c;一台独立的计算机已经无法存储所有的数据---->将大规模的数据存储到成百上千的计算机中------为了解决数据管理以及维护极其繁琐与低效------>分布式文件系统 分布式文件系统是管理网络中跨多台计算机…...

一文读懂select、poll、epoll的用法

select&#xff0c;poll&#xff0c;epoll都是IO多路复用的机制。I/O多路复用就通过一种机制&#xff0c;可以监视多个描述符&#xff0c;一旦某个描述符就绪&#xff08;一般是读就绪或者写就绪&#xff09;&#xff0c;能够通知程序进行相应的读写操作。但select&#xff0c;…...

《C陷阱与缺陷》----词法“陷阱”

导言&#xff1a; 由于一个程序错误可以从不同层面采用不同方式进行考察&#xff0c;而根据程序错误与考察程序的方式之间的相关性&#xff0c;可以将程序错误进行划分为各种陷阱与缺陷&#xff1a; ①.词法“陷阱” ②.语法“陷阱” ③.语义“陷阱” ④.连接问题 ⑤.库函数问…...

千锋教育+计算机四级网络-计算机网络学习-04

UDP概述 UDP协议 面向无连接的用户数据报协议&#xff0c;在传输数据前不需要先建立连接&#xff1b;目地主机的运输层收到UDP报文后&#xff0c;不需要给出任何确认 UDP特点 相比TCP速度稍快些简单的请求/应答应用程序可以使用UDP对于海量数据传输不应该使用UDP广播和多播应用…...

蓝桥杯算法训练合集十四 1.P08052.P07053.同余方程4.P08015.ascii应用

目录 1.P0805 2.P0705 3.同余方程 4.P0801 5.ascii应用 1.P0805 问题描述 当两个比较大的整数相乘时&#xff0c;可能会出现数据溢出的情形。为避免溢出&#xff0c;可以采用字符串的方法来实现两个大数之间的乘法。具体来说&#xff0c;首先以字符串的形式输入两个整数&…...

判断字符串中的字符的类型isdecimal();isalpha();isdigit();isalnum()

【小白从小学Python、C、Java】 【计算机等级考试500强双证书】 【Python-数据分析】 判断字符串中的字符的类型 isdecimal()&#xff1b;isalpha()&#xff1b;isdigit()&#xff1b;isalnum() [太阳]选择题 对于代码中isdecimal()和isalnum()输出的结果是? s "ABc123&…...

VSCode远程调试Linux代码,python解释器配置

安装插件并配置 安装后找到插件图标&#xff0c;点击 点击SSH上的 号 在弹出框中输入命令&#xff1a;ssh usernameip -p port username: 远程服务器的用户名 ip&#xff1a; 远程ip port&#xff1a;端口号&#xff0c;没有可以不用 输入完毕后点击enter 选择ssh配置文件保存…...

03:入门篇 - CTK Plugin Framework 基本原理

作者: 一去、二三里 个人微信号: iwaleon 微信公众号: 高效程序员 CTK Plugin Framework 技术是面向 C++ 的动态模型系统。该系统允许插件之间的松散耦合,并且提供了设计良好的方式来进行功能和数据的交互。此外,它没有预先对插件施加限制,这样就可以很容易地将插件的相关…...

面试攻略,Java 基础面试 100 问(九)

数组有没有 length()方法?String 有没有 length()方法&#xff1f; 数组没有 length()方法&#xff0c;有 length 的属性。String 有 length()方法。JavaScript 中&#xff0c;获得字符串的长度是通过 length 属性得到的&#xff0c;这一点容易和 Java混淆。 在 Java 中&…...

JavaScript 代码不嵌套主义

文章目录前言一、何为嵌套代码二、避免嵌套1.提炼抽取2.反转排列总结前言 看过不少过度嵌套的代码, 我真正意识到问题的严重性是刚入职那会, 我在一个老项目里看到了40个连续的else if, 套了6层的if, for和forEach, 因为我们并没有做什么限制代码嵌套的提前约定. 呃, 那之后认…...

使用默认参数的4大要点

概述 默认参数是C中新增的特性。在C中&#xff0c;可以为函数的参数指定默认值。调用函数时&#xff0c;如果没有指定实参&#xff0c;则自动使用默认参数。默认参数的基本语法这里就不作介绍了&#xff0c;下面重点介绍使用默认参数的一些知识要点。 基本规则 1、当函数中某个…...

Linux文件系统中的硬链接及常见面试题

如果能对inode的概念有所了解&#xff0c;对理解本文会有所帮助。如果对inode的概念不太清楚也没有关系&#xff0c;我们会捎带介绍一下。在文件系统的实现层面&#xff0c;我们可以认为包含两个组件&#xff1a;一个是包含数据块的池子&#xff0c;池子中的数据块是等大小的&a…...

opencv-StereoBM算法

原理解释目前立体匹配算法是计算机视觉中的一个难点和热点&#xff0c;算法很多&#xff0c;但是一般的步骤是&#xff1a;A、匹配代价计算匹配代价计算是整个立体匹配算法的基础&#xff0c;实际是对不同视差下进行灰度相似性测量。常见的方法有灰度差的平方SD&#xff08;squ…...

图像分类竞赛进阶技能:OpenAI-CLIP使用范例

OpenAI-CLIP 官方介绍 尽管深度学习已经彻底改变了计算机视觉&#xff0c;但目前的方法存在几个主要问题:典型的视觉数据集是劳动密集型的&#xff0c;创建成本高&#xff0c;同时只教授一组狭窄的视觉概念;标准视觉模型擅长于一项任务且仅擅长于一项任务&#xff0c;并且需要大…...

Metasploit框架基础(一)

文章目录前言一、基础认知二、批量POC/EXP的构想三、poc检测框架的简单实现四、xray五、Meatsploit框架参考前言 Metasploit 一款渗透测试框架漏洞利用的集合与构建和定制满足你的需求的基础漏洞利用和验证的工具 这几个说法都是百度或者官方文档中出现的手法&#xff0c;说…...

pytorch零基础实现语义分割项目(二)——标签转换与数据加载

数据转换与加载项目列表前言标签转换RGB标签到类别标签映射RGB标签转换成类别标签数据数据加载随机裁剪数据加载项目列表 语义分割项目&#xff08;一&#xff09;——数据概况及预处理 语义分割项目&#xff08;二&#xff09;——标签转换与数据加载 语义分割项目&#x…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...