Round829 Div2 E

zzyNorthPole
  2023-04-07 19:53:35 2023-04-07 19:53:35 Created   2024-02-06 11:30:48 2024-02-06 11:30:48 Updated      

题目描述

给定一个01序列，随机从中选出两个位置，当且时，交换和。问交换成为有序序列的期望步数是多少。

解题思路

本题主要是观察序列中的收敛模型。最后的状态显然是所有的在前面，而所有的在后面。假设的个数为，那么之间的是必须要被换出，而中的必须要被换入。因此在区间内的交换是无效的，只有在两个区间之间的交换是有效的。因此可以考虑动态规划。记为在中有个的情况下，成为有序序列的期望步数。则状态转移方程为，整理后为.

补档，太摸了太摸了😆

  • Title: Round829 Div2 E
  • Author: zzyNorthPole
  • Created at : 2023-04-07 19:53:35
  • Updated at : 2024-02-06 11:30:48
  • Link: https://zzynorthpole.github.io/2023/04/07/Round829-Div2-E/
  • License: This work is licensed under CC BY-NC-SA 4.0.
On this page
Round829 Div2 E
  1. 题目描述
  2. 解题思路