• 售前

  • 售后

热门帖子
入门百科

CF1621G Weighted Increasing Subsequences(离散化+树状数组优化dp+栈维护

[复制链接]
永远丶并不远 显示全部楼层 发表于 2022-1-15 21:20:06 |阅读模式 打印 上一主题 下一主题
problem

luogu-link
solution

显然单独思量每个                               i                          i               i 的贡献,即被多少个合法上升子序列包罗。
令                               x                      =                      max                      ⁡                      {                      j                                             ∣                                             j                      >                      i                      ∧                               a                         j                              >                               a                         i                              }                          x=\max\{j\ |\ j>i\wedge a_j>a_i\}               x=max{j ∣ j>i∧aj​>ai​},则包罗                               i                          i               i 的合法子序列的末了元素最远只能到                               x                      −                      1                          x-1               x−1。
发现,告急的不是值自己,而是巨细关系。全部可以离散化从小到大标号                                    1                         ∼                         n                              1\sim n                  1∼n,权值小的放前面;权值雷同下标大的放前面
下面的                               a                          a               a 均表现离散化后的序列。
同时将合法上升子序列拆分成正着以                                    i                              i                  i 末了的上升子序列和倒着以                                    i                              i                  i 末了的降落子序列两个部分,分别求出方案数后乘法原理即可。
                               1                      ∼                      i                          1\sim i               1∼i 以                               i                          i               i 末了的上升子序列,在已经离散化后,预处理惩罚就非常简单了。树状数组维护                                        f                         i                              :                      i                          f_i:i               fi​:i 末了的上升子序列个数。
然后思量                               x                      −                      1                      ∼                      i                          x-1\sim i               x−1∼i 以                               i                          i               i 末了的降落子序列。
由于每个                               i                          i               i 对应的                               x                          x               x 不一样,不能像预处理惩罚一样只扫描一遍整个                               1                      ∼                      n                          1\sim n               1∼n,也不大概每次都去遍历这个区间。
不妨思量转化成                                   n                         ∼                         i                              n\sim i                  n∼i 以                                    i                              i                  i 末了的降落子序列个数减去以                                    x                              x                  x 开头以                                    i                              i                  i 末了的个数
                               n                      ∼                      i                          n\sim i               n∼i 以                               i                          i               i 末了的降落子序列个数,预处理惩罚方法同上。
末了就只剩下以                               x                          x               x 开头以                               i                          i               i 末了的降落子序列个数的盘算了,开头和末了都已经定了,是可做的。

设                               y                      :                               a                         y                              =                      max                      ⁡                      {                               a                         j                                                     ∣                                             x                      <                      j                      ≤                      n                      }                          y:a_y=\max\{a_j\ |\ x

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作