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

题解:AT_arc068_d [ARC068F] Solitaire

简单数数。

题意:很简单了,不再赘述。

做法:

首先我们考虑这个 deque 里面的数是什么样子的,发现一定是个谷型并且 \(1\) 是谷底,这个显然,那么就意味着,对于前 \(k-1\) 个位置是可以分成两个下降序列,然后 \(k\) 之后的一定是一个有序序列从前从后随便取得到的,这个部分的贡献是一定的,为 \(2^{n-k-1}\),因为每次随便选前面和后面都可以,一定不重复。

那么我们考虑前面那个贡献,但是我们发现如果描述成两个下降序列的话非常困难,因为很容易重复计算,但是我们注意到谷型一个很好的性质:如果我们目前最小值为 \(x\),那么下一个数可以是比 \(x\) 更小的,否则就是唯一固定的。

所以我们考虑一个 dp,\(dp_{i,j}\) 代表用了 \(i\) 个数,最小值为 \(j\),转移有两种,一种是我下一个数填 \(<j\) 的,也就是对 \(dp_{i+1,1\cdots j-1}\) 进行转移。还有一种是我填一个大于 \(j\) 的,这个数虽然我们不知道,但是一定是另一侧的顶端是唯一的,所以也是可以转移的,但是要求 \(i\not=n-j+1\) 即还有比我大的数才行,转移到 \(dp_{i+1,j}\)

记得最后乘上 \(2^{n-k-1}\)

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

相关文章:

  • Codeforces Round 1051 (Div. 2) D1D2题解
  • JSP
  • 每日博客
  • 探展打卡 Serverless,2025 云栖大会来了
  • 从 0 到 1,AI 走进服装店:记住每位顾客的喜好,比你还靠谱
  • STM32HAL 飞快入门(十九):UART 编程(二)—— 中断方式实现收发及局限分析
  • 贪心算法应用:多重背包启发式疑问详解
  • 划重点|云栖大会「AI 原生应用架构论坛」看点梳理
  • 君子如水,心中有火:vivo本心而为30周年
  • Margin 塌陷问题如何解决?触发BFC。BFC的概念和触发条件
  • 9.22
  • 数字统计
  • 火速收藏!2025 云栖大会 AI 中间件议程看点全公开(附免费报名通道)
  • 第二次软工作业——个人项目 - LXJ
  • WinForm引入项目资源文件
  • 第二次作业
  • 训练集,验证集,测试集
  • Android 项目:画图白板APP开发(六)——分页展示 - 教程
  • ESP32 读取旋转编码器
  • mysql/oracle LEFT JOIN 取时间最大的数据
  • 6月6日证书 - 工信部人才交流中心PostgreSQL中级PGCP高级PGCM认证
  • 基于遗传算法与非线性规划的混合优化算法在电力系统最优潮流中的实现
  • 【下一款产品】
  • 数1的个数
  • 通过ML.Net调用Yolov5的Onnx模型
  • Java-如何在Eclipse开发-数组
  • 常用数据生成器
  • 基于RSSI修正的定位算法分析
  • c# 反射动态添加Attribute
  • MyBatis-Plus 全方位深度指南:从入门到精通