[ABC400F] Happy Birthday! 3 题解
考虑正难则反。问题转化为：
一个环上有 n n n 个物品，颜色分别为 c o l i col_i coli，每次操作选择两个数 i , j i, j i,j 使得 ∀ k ∈ [ i , j ] , c o l k = c o l i ∨ c o l k = 0 \forall k \in [i, j], col_k = col_i \lor col_k = 0 ∀k∈[i,j],colk=coli∨colk=0，将 [ i , j ] [i, j] [i,j] 中的每个物品的颜色都设为 0 0 0。（下文将这种操作称为“漂白”。）一次操作的代价为 j − i + 1 + x c o l i j - i + 1 + x_{col_i} j−i+1+xcoli。求将整个环漂白的最小总代价。
先断环为链。设 d p i , j dp_{i, j} dpi,j 表示将 [ i , j ] [i, j] [i,j] 漂白的最小代价，那么显然有 d p i , j = min k = i j − 1 d p i , k + d p k + 1 , j dp_{i, j} = \min_{k = i}^{j - 1} dp_{i, k} + dp_{k + 1, j} dpi,j=mink=ij−1dpi,k+dpk+1,j。
设 f i , j f_{i, j} fi,j 表示使 [ i , j ] [i, j] [i,j] 能够漂白的最小代价，那么显然有 f i , j = min k = 1 j − 1 f i , k + d p k + 1 , j f_{i, j} = \min_{k = 1}^{j - 1} f_{i, k} + dp_{k + 1, j} fi,j=mink=1j−1fi,k+dpk+1,j。当 c o l i = c o l j col_i = col_j coli=colj 时，有 f i , j = min ( f i , j , f i , j − 1 ) , d p i , j = min ( d p i , j , f i , j + j − i + x c o l i ) f_{i, j} = \min (f_{i, j}, f_{i, j - 1}), dp_{i, j} = \min (dp_{i, j}, f_{i, j} + j - i + x_{col_i}) fi,j=min(fi,j,fi,j−1),dpi,j=min(dpi,j,fi,j+j−i+xcoli)。
答案即为 min i = 1 n d p i , i + n − 1 \min_{i = 1}^n dp_{i, i + n - 1} mini=1ndpi,i+n−1。
相关文章：
[ABC400F] Happy Birthday! 3 题解
考虑正难则反。问题转化为： 一个环上有 n n n 个物品，颜色分别为 c o l i col_i coli，每次操作选择两个数 i , j i, j i,j 使得 ∀ k ∈ [ i , j ] , c o l k c o l i ∨ c o l k 0 \forall k \in [i, j], col_k col_i \lor col_k …...
使用nuxt3+tailwindcss4+@nuxt/content3在页面渲染 markdown 文档
nuxt3tailwindcss在页面渲染 markdown 文档 页面效果 依赖 “nuxt/content”: “^3.4.0” “tailwindcss”: “^4.0.10” “nuxt”: “^3.16.2” “tailwindcss/vite”: “^4.0.10” tailwindcss/typography (这个是格式化 md 样式用的) 注意： 这里nuxt/content…...
：字节最新表情+动作模仿视频生成DreamActor-M1)
畅游Diffusion数字人(23)：字节最新表情+动作模仿视频生成DreamActor-M1
畅游Diffusion数字人(0)：专栏文章导航 前言：之前有很多动作模仿或者表情模仿的工作，但是如果要在实际使用中进行电影级的复刻工作，仅仅表情或动作模仿还不够，需要表情和动作一起模仿。最近字节跳动提出了一个表情+动作模仿视频生成DreamActor-M1。 目录 贡献概述 核心动…...
多模态学习分析（MLA）驱动高中差异化教学策略研究
一、引言 1.1 研究背景 在当今时代，教育数字化转型的浪潮正席卷全球，深刻地改变着教育的面貌。这一转型不仅是技术的革新，更是教育理念、教学模式和教育管理的全面变革。随着互联网、大数据、人工智能等现代信息技术在教育领域的广泛应用&a…...
为什么ASCII的A是65[特殊字符]
为什么ASCII的A是65 1. ASCII是怎么来的 ASCII是1960年代美国标准协会制定的，目的是统一计算机字符编码。它们要在**7个比特位（0-127）**里，塞下所有英文字符，数字，标点和控制符。 2. 为什么A是65&#x…...
Python正则表达式实战技巧：如何高效处理文本匹配？
当你需要在Python中处理文本数据时，正则表达式绝对是你的瑞士军刀。无论是数据清洗、日志分析还是表单验证，掌握正则表达式都能让你事半功倍。今天我们就来聊聊Python中re模块的那些实用技巧和常见陷阱。 为什么正则表达式如此重要？ 想象一…...
驱动学习专栏--写在前面
此专栏基于正点原子的文档【正点原子】I.MX6U嵌入式Linux驱动开发指南V1.81 开发板为luckfox的rv1106开发板，之前参加过一个CM1相机的开源项目，与其吃灰不如作为一个学习的工具来发挥余热 所以文档中的一些东西需要对应的在rv1106平台上做修改ÿ…...
Java中的Map vs Python字典：核心对比与使用指南
一、核心概念 1. 基本定义 Python字典（dict） ：动态类型键值对集合，语法简洁，支持快速查找。Java Map：接口，常用实现类如 HashMap、LinkedHashMap，需声明键值类型（泛型&…...
从零搭建微服务项目Pro（第0章——微服务项目脚手架搭建）
前言： 在本专栏Base第0章曾介绍一种入门级的微服务项目搭建，尽管后续基于此框架上实现了Nacos、Eureka服务注册发现、配置管理、Feign调用、网关模块、OSS文件存储、JSR参数校验、LogBack日志配置，鉴权模块、定时任务模块等，但由于…...
)
RAG创建向量数据库：docsearch = FAISS.from_texts(documents, embeddings)
RAG创建向量数据库：docsearch = FAISS.from_texts(documents, embeddings) 代码解释 docsearch = FAISS.from_texts(documents, embeddings) 这行代码主要作用是基于给定的文本集合创建一个向量数据库（这里使用 FAISS 作为向量数据库工具 ）。具体说明如下： FAISS ：FAISS …...
适配python3.9的 SORT算法
简单地更改了 sort.py 函数的接口，核心思想、处理操作并不改变。 源代码链接：https://github.com/abewley/sort import os import numpy as np import glob import time import argparse from filterpy.kalman import KalmanFilter from scipy.optimiz…...
记录Docker部署CosyVoice V2.0
#记录工作 CosyVoice 是由 FunAudioLLM 团队开发的一个开源多语言大规模语音生成模型，提供了从推理、训练到部署的全栈解决方案。 项目地址： https://github.com/FunAudioLLM/CosyVoice.git 该项目目前从v1.0版本迭代到v2.0版本，但是在Wind…...
源码编译 Galera、MySQL 5.7 Wsrep 和安装 MySQL 5.7 Galera集群
源码编译 Galera、MySQL 5.7 Wsrep 和安装 MySQL 5.7 Galera集群 说明1、源码编译 Galera1.1、安装依赖1.2、源码编译安装 openSSL1.2.1、下载源码1.2.2、编译安装 1.3、源码编译安装 Galera 31.3.1、下载源码1.3.2、注意1.3.3、编译安装 2、源码编译 MySQL-Wsrep2.1、安装依赖…...
【SLAM】ubuntu 18.04 下 OpenCV 3.2.0 的 opencv_example 运行闪退
本文首发于❄慕雪的寒舍 ubuntu 18.04 下 OpenCV 3.2.0 的 opencv_example 运行闪退问题探究。 1. 问题说明 在之前的ORB-SLAM3项目于ROS运行的博客中，提到过安装ROS时会自己安装一个OpenCV 3.2.0版本，所以最好不要安装其他版本的OpenCV，避…...
Linux网络编程——数据链路层详解，以太网、MAC地址、MTU、ARP、DNS、NAT、代理服务器......
目录 一、前言 二、以太网 二、以太网帧格式 三、 MAC地址 四、MTU 1、数据链路层的数据分片 2、MTU对UDP协议的影响 3、MTU对TCP协议的影响 五、ARP协议 1、什么是ARP 2、ARP的作用 3、ARP协议的工作流程 4、ARP缓存表 5、ARP请求报文 6、中间人 六、DNS&…...
Android7 Input（四）InputReader
概述 本文主要描述了Android Input框架中的InputReader的功能，InputReader模块的功能，总结成一句话就是InputReader获取输入设备的事件并将事件进行加工处理，然后传递给QueuedInputListener，最终QueuedInputListener将事件传递给…...
游戏报错？MFC140.dll怎么安装才能解决问题？提供多种MFC140.dll丢失修复方案
MFC140.dll 是 Microsoft Visual C 2015 运行库的重要组成部分，许多软件和游戏依赖它才能正常运行。如果你的电脑提示 "MFC140.dll 丢失" 或 "MFC140.dll 未找到"，说明系统缺少该文件，导致程序无法启动。本文将详细介绍 …...
寻找最大美丽数
# 输入：nums1 [4,2,1,5,3], nums2 [10,20,30,40,50], k 2 # 输出：[80,30,0,80,50] import random class Solution:def findMaxSum(self, nums1, nums2, k):hash_table []sum1 0data []print(**31,\n,\t数据)for key,values in enumerate(nums1):da…...
[Linux]进程地址空间
前言 我们在学习C语言期间，经常可以提及到这些区域，有一个问题：这里的地址空间是内存吗？答案是这里的地址空间并不是内存。这里的地址空间是进程地址空间，下面我们就讲解进程地址空间。 这段空间中自下而上ÿ…...
dfs和bfs算法
DFS（深度优先搜索，Depth-First Search）和 BFS（广度优先搜索，Breadth-First Search）是图遍历或搜索算法中的两种基本方法。它们在探索图的节点时采用不同的策略，适用于不同的场景。 ### 深度优先…...
跨站请求是什么？
介绍 跨站请求（Cross-Site Request）通常是指浏览器在访问一个网站时，向另一个域名的网站发送请求的行为。这个概念在 Web 安全中非常重要，尤其是在涉及到“跨站请求伪造（CSRF）”和“跨域资源共享ÿ…...
【深度学习与大模型基础】第9章-条件概率以及条件概率的链式法则
简单理解条件概率 条件概率就是在已知某件事发生的情况下，另一件事发生的概率。用数学符号表示就是： P(A|B) 在B发生的前提下，A发生的概率。 计算机例子：垃圾邮件过滤 假设你写了一个程序来自动判断邮件是否是垃圾邮件…...
C++: 获取auto的实际类型
auto a "hello";auto* b "hello";auto& c "hello";上述 a, b, c 类型分别是什么？ 在不使用 IDE 提供的 inlay hints 情况下， 可以编译期获取，然后运行时打印出来: 方法： 用 decltype(var)…...
谷歌开源代理开发工具包（Agent Development Kit，ADK）：让多智能体应用的构建变得更简
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗？订阅我们的简报，深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同，从行业内部的深度分析和实用指南中受益。不要错过这个机会，成为AI领…...
揭开人工智能与机器学习的神秘面纱：开发者的视角
李升伟 编译 人工智能（AI）和机器学习（ML）早已不再是空洞的流行语——它们正在彻底改变我们构建软件、做出决策以及与技术互动的方式。无论是自动化重复性任务，还是驱动自动驾驶汽车，AI/ML都是现代创新的核…...
35.Java线程池（线程池概述、线程池的架构、线程池的种类与创建、线程池的底层原理、线程池的工作流程、线程池的拒绝策略、自定义线程池）
一、线程池概述 1、线程池的优势 线程池是一种线程使用模式，线程过多会带来调度开销，进而影响缓存局部性和整体性能，而线程池维护着多个线程，等待着监督管理者分配可并发执行的任务，这避免了在处理短时间任务时创建与…...
【NumPy科学计算：高性能数组操作核心指南】
目录 前言：技术背景与价值当前技术痛点解决方案概述目标读者说明 一、技术原理剖析核心概念图解关键技术模块技术选型对比 二、实战演示环境配置要求核心代码实现运行结果验证 三、性能对比测试方法论量化数据对比结果分析 四、最佳实践推荐方案 ✅常见错误 ❌调试技…...
软考 系统架构设计师系列知识点之杂项集萃（50）
接前一篇文章：软考 系统架构设计师系列知识点之杂项集萃（49） 第78题 著作权中，（）的保护期不受限制。 A. 发表权 B. 发行权 C. 署名权 D. 展览权 正确答案：C。 所属知识点：旧版…...
实现定长的内存池
池化技术 所谓的池化技术，就是程序预先向系统申请过量的资源，然后自己管理起来，以备不时之需。这个操作的价值就是，如果申请与释放资源的开销较大，提前申请资源并在使用后并不释放而是重复利用，能够提高程序…...
：铜锁和BoringSSL)
定制一款国密浏览器(7)：铜锁和BoringSSL
上一章简单介绍了一下国密算法，本章开始进入实战，进行国密算法的移植。算法的移植以铜锁为蓝本，移植到 BoringSSL 中。 BoringSSL 也是由 OpenSSL fork 而来，那能否修改 Chromium 的源码，使用铜锁库呢？这种方式我也考虑并尝试过，最后发现两者的接口差别太大，Chromium …...
Docker 安装CRMEB陀螺匠教程
首先下载代码到服务器中，打开终端，并切换到项目源码根目录： 通过 Docker compose 启动项目 第一次启动时需要拉取和打包相关镜像，所需时长视网络情况而定，需耐心等待。 配置反向代理 参考 Nginx 配置 Nginx 反向代…...
Java中的static都能用来修饰什么？
在Java编程语言中，static关键字是非常重要的修饰符，可以用于多种不同的地方。可用来修饰变量、方法、代码块以及类。 1.静态变量 定义：静态变量属于类本身，而不是类的任何特定实例（new出来的对象）。 特点&a…...
词法分析器设计实验
掌握生成词法分析器的方法，加深对词法分析原理的理解。掌握设计、编制并调试词法分析程序的思想和方法。本实验是高级语言程序设计、数据结构和编译原理中词法分析原理等知识的综合。 【实验内容及要求】完善以下代码(红色标注处)并加上注释(蓝色标注处) int Getsym…...
matlab求和∑函数方程编程？
matlab求和∑函数方程编程？ 一 题目：求下列函数方程式的和 二：代码如下： >> sum_result 0; % 初始化求和变量 for x 1:10 % 设…...
Vue3.5 企业级管理系统实战（十四）：动态主题切换
动态主题切换是针对用户体验的常见的功能之一，我们可以自己实现如暗黑模式、明亮模式的切换，也可以利用 Element Plus 默认支持的强大动态主题方案实现。这里我们探讨的是后者通过 CSS 变量设置的方案。 1 组件准备 1.1 修改 Navbar 组件 在 src/layo…...
, zip(), enumerate()等)
Python中for循环及其相关函数range(), zip(), enumerate()等
一、Python中的for循环及其相关函数 Python的for循环是算法竞赛中最常用的迭代工具之一，因其简洁和灵活性非常适合快速实现逻辑。以下详细讲解for循环及相关函数在竞赛中的使用场景。 1. for循环基本语法 Python的for循环用于遍历可迭代对象（如列表、…...
数据结构与算法——链表OJ题详解（2）
文章目录 一、前言二、OJ续享2.1相交链表2.2环形链表12.2环形链表2 三、总结 一、前言 哦了兄弟们，咱们上次在详解链表OJ题的时候，有一部分OJ题呢up并没有整理完，这一个星期呢，up也是在不断的学习并且沉淀着，也是终于…...
免费送源码：Java+ssm+MySQL 基于PHP在线考试系统的设计与实现 计算机毕业设计原创定制
摘 要 信息化社会内需要与之针对性的信息获取途径，但是途径的扩展基本上为人们所努力的方向，由于站在的角度存在偏差，人们经常能够获得不同类型信息，这也是技术最为难以攻克的课题。针对在线考试等问题，对如何通过计算…...
Android之JNI详解
Android之JNI详解 简介创建项目注册动态注册静态注册 关键词解读基础数据类型引用java对象JNI引用与释放cmake配置文件 简介 JNI（Java Native Interface） 是 Java 提供的一种编程框架，用于在 Java 应用程序中调用和与用其他编程语言…...
React Hooks: useRef，useCallback，useMemo用法详解
1. useRef（保存引用值） useRef 通常用于保存“不会参与 UI 渲染，但生命周期要长”的对象引用，比如获取 DOM、保存定时器 ID、WebSocket等。 新建useRef.js组件，写入代码： import React, { useRef, useSt…...
Java基础知识
概念 请介绍全局变量和局部变量的区别 Java中的变量分为成员变量和局部变量，它们的区别如下： 成员变量： 1. 成员变量是在类的范围里定义的变量； 2. 成员变量有默认初始值； 3. 未被static修饰的成员变量也叫…...
体验智能体构建过程：从零开始构建Agent
1. 什么是智能体？ 智能体（Agents）是一种能够感知环境、做出决策并采取行动来实现特定目标的自主实体。智能体的复杂程度各不相同，从简单的响应式智能体（对刺激直接做出反应）到更高级的智能体（能…...
如何从项目目标到成功标准：构建可量化、可落地的项目评估体系
引言 在项目管理领域，"项目成功"的定义往往比表面看起来更复杂。根据PMI的行业报告，67%的项目失败源于目标与成功标准的不匹配。当项目团队仅关注"按时交付"或"预算达标"时，常会忽视真正的价值创造。本文将通…...
)
大模型论文：Language Models are Few-Shot Learners(GPT3)
大模型论文：Language Models are Few-Shot Learners(GPT3) 文章地址：https://proceedings.neurips.cc/paper_files/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf 一、摘要 我们证明了，扩大语言模型的规模在任务无关的 few…...
驱动学习专栏--字符设备驱动篇--1_chrdevbase
字符设备驱动简介 字符设备是 Linux 驱动中最基本的一类设备驱动，字符设备就是一个一个字节，按照字节 流进行读写操作的设备，读写数据是分先后顺序的。比如我们最常见的点灯、按键、 IIC 、 SPI ， LCD 等等都是字符设备&…...
muduo库源码分析: TcpConnection
一. 主要成员: socket_：用于保存已连接套接字文件描述符。channel_：封装了上面的socket_及其各类事件的处理函数（读、写、错误、关闭等事件处理函数）。这个Channel中保存的各类事件的处理函数是在TcpConnection对象构造函数中注册…...
【SLAM】ubuntu 18.04 编译安装 OpenCV 3.2.0 时出现哈希错误
本文首发于❄慕雪的寒舍 1. 前言 1.1. 问题说明 在amd64的ubuntu 18.04 desktop上编译安装 OpenCV 3.2.0 的时候，我遇到了cmake构建错误。错误的核心报错如下 for file: [/home/king/slam/pkg/opencv-3.2.0/3rdparty/ippicv/downloads/linux-808b791a6eac9ed78d32…...
挂马漏洞 asp连接冰蝎webshell (附webshell源码 仅限学习研究）
目录 ASP WebShell代码 代码说明： 部署步骤： 使用冰蝎客户端连接： 注意事项： ASP WebShell代码 <% 冰蝎连接密码（需与冰蝎客户端配置一致） Dim key key "mysecretkey123" 自定义密码…...
Grafana将弃用AngularJS-我们该如何迁移
AngularJS 弃用时间线 AngularJS 支持已在 Grafana 9 中正式弃用。在 2024 年 5 月发布的 Grafana 11 中，所有 Grafana Cloud 和自托管安装默认关闭该功能。到 Grafana 12 版本时，将完全移除对 AngularJS 的支持，包括配置参数开关 angular_s…...