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

题2

前言:为什么不放在题 1

因为题 \(1\) 收录的有点多了,现在编辑框都卡。预计加上 code 1300 行就要开新的了。

正文

AT_dp_t

如果设计状态为 \(f_{i,j}\) 表示考虑到前 \(i\) 个数第 \(i\) 个数为 \(j\) 的话将很难转移,因为这是排列,不能有重复。要是把前面的值都记下来就是暴力了。

什么东西不需要保证不重复呢又能转移呢?答案是排名,但是排名肯定不能重复吧?这里所说的是局部的排名,可以想象成动态的离散化,比如你先填了 \(1, 3, 5, 6\) 那排名为 \(1, 2, 3 ,4\),然后填了个 \(2\) 那排名就是 \(1, 3, 4, 5, 2\)

考虑 \(f_{i, j}\) 表示前 \(i\) 个数最后一个数在这 \(i\) 个数中排名为 \(j\) 的方案数,这样的话就可以不考虑重复了。转移是显然的,前缀和优化即可。

有一个问题:为什么 \(f_{1, 1}\)\(1\) 而不是 \(n\), 这是因为我们 dp 的过程中和值是无关的,最后得到的是一个全局的排名序列,显然这也是这个排列,比如最后排名为 \(5, 3, 2, 1, 4\) 那排列就是 \(5, 3, 2, 1, 4\), 所以只需要记录局部排名即可。

时间复杂度 \(\mathcal{O}(n^2)\)

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

相关文章:

  • linux命令-rm
  • 2025.9.26
  • 基于Amazon S3设置AWS Transfer Family Web 应用程序 - 实践
  • 作为 PHP 开发者,我第一次用 Go 写了个桌面应用
  • JBoltAI智能出题助手:助力高效学习与知识巩固 - 那年-冬季
  • JBoltAI设备智能检测:为设备管理维护提供高效辅助 - 那年-冬季
  • JBoltAI:Java与AI的完美融合,赋能技术团队新未来 - 那年-冬季
  • AIGS与AIGC:人工智能时代的范式跃迁与价值重构 - 那年-冬季
  • 5
  • ?模拟赛(3) 赛后总结
  • 用鼠标滚轮缩放原理图界面的小工具
  • 实验任务1
  • OI界的梗(继 @CCCsuper 2.0 版本)
  • 9/26
  • Python 私有属性深度解析
  • 菜鸟记录:c语言实现洛谷P1219 ———八皇后
  • 当危机爆发时,所有网络安全都是本地的
  • crc校验原理是什么?
  • CF1385D a-Good String
  • 9月23日(日记里有)
  • 9月25日(日记里有)
  • Git 提交代码前,一定要做的两件事
  • 本地调试接口时遇到的跨域问题,十分钟解决
  • 用 Excel 快速处理接口返回的 JSON 数据
  • 调度的基本概念
  • Overleaf项目文件同步工具: olsync
  • CF1995D Cases
  • 日志| 编辑距离 | 最长有效括号 |
  • day5
  • 《etcd库——键值存储系统》 - 教程