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

AtCoder-abc228_h Histogram题解

题目链接

题目大意

给定一段长度为\(n\)的数组\(a\)\(c\),表示\(i\)的大小和将 \(a_i+1\) 的费用。如果最后剩\(k\)个不同的\(a_i\)就将费用加上 \(X\times k\)

题目分析

首先该题想让我们的最后剩下的 \(a_i\) 个数最少,那我们就没必要创造新的 \(a_i\) 。所以最后的\(a_i\)序列一定是

\[a_{b_1},a_{b_1}···a_{b_1}|a_{b_2},a_{b_2}···a_{b_2}|a_{b_m},a_{b_m}···a_{b_m} \]

即一段连续的\(a_i\)
假设\(dp_i\)为以\(i\)为结尾的最小代价
先将\(a\)数组和\(c\)数组按\(a_i\)大小排序。建个结构体或\(\mathrm{pair}\)就行。这样后面就不用绝对值了。

\[dp_i \min \limits_{j=1}^{i}=\left(dp_{j-1}+\sum_{k=1}^{j}c_k(a_i-a_k)+X \right) \]

\((a_i-a_k)\)这一项不好处理,所以把\(\sum\)拆开。

\[dp_i \min \limits_{j=1}^{i}=\left(dp_{j-1}+\sum_{k=1}^{j}c_k\times a_i-\sum_{k=1}^{j}c_k\times a_k+X \right) \]

然后把\(\sum\)用前缀和替代。

\(s1_i=\sum\limits_{j=1}^{i}c_j\)

\(s2_i=\sum\limits_{j=1}^{i}c_j\times a_j\)

\[dp_i \min \limits_{j=1}^{i}=\left(dp_{j-1}+a_i\times\left(s1_i-s1_{j-1}\right)-(s2_i-s2_{j-1})+X \right) \]

然后这个式子看起来就很斜率优化。式子左边化简

\[dp_{j-1}+a_is1_i-a_is1_{j-1}-s2_i+s2_{j-1}+X \]

我们考虑两个数\(j_1\)\(j_2\)。当\(j_1\)\(j_2\)更优势,式子为

\[dp_{j1-1}+a_is1_i-a_is1_{j1-1}-s2_i+s2_{j1-1}+X\le dp_{j2}+a_is1_i-a_is1_{j2-1}-s2_i+s2_{j2-1}+X \]

消去不含\(j\)的项

\[dp_{j1-1}-a_is1_{j1-1}+s2_{j1-1}\le dp_{j2-1}-a_is1_{j2-1}+s2_{j2-1} \]

移项

\[dp_{j1-1}-dp_{j2-1}+s2_{j1-1}-s2_{j2-1}\le a_is1_{j1-1}-a_is1_{j2-1} \]

右边都有\(a_i\),合并一下

\[dp_{j1-1}-dp_{j2-1}+s2_{j1-1}-s2_{j2-1}\le a_i\left(s1_{j1-1}-s1_{j2-1}\right) \]

把左边含有\(j\)的除到右边

\[\frac{dp_{j1-1}-dp_{j2-1}+s2_{j1-1}-s2_{j2-1}}{s1_{j1-1}-s1_{j2-1}}\le a_i \]

然后调整一下

\[\frac{\left(dp_{j1-1}+s2_{j1-1}\right)-\left(dp_{j2-1}+s2_{j2-1}\right)}{s1_{j1-1}-s1_{j2-1}}\le a_i \]

这样就行了。\(Y\)就是\(dp_{j-1}+s2_{j-1}\),\(X\)就是\(s1_{j-1}\)

然后就完事了

http://www.hskmm.com/?act=detail&tid=33563

相关文章:

  • 公钥私钥概念
  • 2025 年融合瓦生产厂家最新推荐排行榜:TPS/TPO/TPF 塑钢及钢塑一体融合瓦企业盘点与品质解析
  • 2025 年防腐瓦源头厂家最新推荐榜:聚焦塑钢防腐瓦 / PSP 塑钢覆合防腐瓦板等多类型产品,精选优质企业助力精准采购决策
  • python第五天
  • 2025 年碳源厂家最新推荐排行榜:复合 / 污水处理 / 微生物 / 液体 / 乙酸钠碳源品牌综合实力深度解析
  • 2025年10月AI搜索优化推荐榜单:十强服务商对比评测与避坑指南
  • uml九种类图介绍
  • 2025 年试验箱厂家最新推荐排行榜:涵盖高低温 / 恒温恒湿 / 冷热冲击等设备,精选研发实力强、质量管控严的优质品牌
  • 撼嗡幌佣渍话仝使卮哺
  • 2025年10月geo优化服务商推荐榜:十强对比评测与中立选购指南
  • 2025年10月geo优化服务商推荐榜单:聚焦全平台同步优化能力的客观剖析
  • 2025 年试验台厂家最新推荐排行榜:聚焦振动 / 三轴向 / 垂直等类型,精选优质企业助您精准选型
  • 2025年10月geo优化推荐排行:基于技术实力与案例成效的权威评测榜
  • 2025 年 PET 薄膜源头厂家最新推荐榜单:光学 / 高温 / 阻燃 / 抗静电 / 无胶覆合PET 薄膜等多类型薄膜企业精选及行业适配案例详解
  • 2025 年最新推荐!国内软水品牌实力排行榜揭晓,西岭百年等优质品牌深度解析健身喝水极/天然/西岭百年极/弱碱性天然极软水厂家推荐
  • CF1463C
  • 2025年10月geo优化推荐榜单:聚焦跨平台效果与行业复购数据的全面剖析
  • 2025年10月deepseek排名优化推荐对比评测:聚焦技术深度与服务完整度的客观剖析
  • 2025年10月deepseek排名优化推荐榜单:十强服务商多维对比与中立评测
  • 2025 年废纸输送机优质厂家最新推荐榜单:技术实力与市场口碑双维度甄选企业品牌不切断文丘里装置/不锈钢金属软管/废纸爬坡输送机厂家推荐
  • 2025 年最新推荐铝单板厂家榜单:冲孔 / 木纹 / 双曲 / 氟碳 / 雕花 / 天花 / 外墙 / 金属 / 异型 / 石纹铝单板优选品牌推荐
  • 2025 年保温钢管生产厂家最新推荐排行榜:聚焦优质企业核心优势,助力精准选购名单发布兰州无缝保温钢管/兰州焊接保温钢管/兰州聚氨酯保温钢管/兰州聚氨酯聚乙烯保温钢管厂家推荐
  • logstash
  • 歉痰孜缎谇谈棵盎温奈
  • 10 18
  • 2025 年国内空调机组厂家最新品牌推荐,含冷凝热回收等多类型空调机组企业优选指南!海水源养殖热泵/精密机房/岗位送风/蒸发冷空调机组厂家推荐
  • docker下运行ollama及deepseek
  • 2025 年最新推荐!空压机租赁公司综合实力推荐榜单:涵盖无油 / 高压 / 阿特拉斯等机型及二手设备买卖置换,助力企业精准挑选服务商
  • 2025年10月AI搜索营销推荐排名:结合头部案例与合规资质的中立评价