首页 > 其他 > 详细

CF850F Rainbow Balls 题解

时间:2020-08-14 01:51:39      阅读:57      评论:0      收藏:0      [点我收藏+]

考虑最后变成哪一种颜色。
\(s = \sum\limits_{i=1}^n a_i\)
设现在有 \(k\) 种当前颜色, 需要全部变成该种颜色, 期望步数为 \(f_k\)
考虑状态转移。设 \(p\) 为取出两个球颜色不同的概率。
\(f_i = (f_{i+1} + f_{i-1})p + (1 - 2p)f_i + v_i\)
考虑 \(v_i\)。由于我们考虑的 \(dp\) 是要求最后颜色是一定的,所以不能算上答案不是该颜色的答案。所以 \(v_i\) 就是最终颜色为这种颜色的概率。
如果颜色变动了,而让另一种颜色变成该颜色和该颜色变成另一种颜色的概率是一样的,所以 \(v_i = \frac{1}{2}(v_{i-1} + v_{i+1})\)
所以 \(2v_i = v_{i-1} + v_{i+1}\), \(v_{i+1} - v_i = v_i - v_{i-1} (= t)\)
\(v_0 = 1, v_s = 1\)

\[1 = v_s - v_0 = \sum\limits_{i=1}^s v_i - v_{i-1} = st \]

所以 \(t = \frac{1}{s}\), \(v_i = \frac{i}{s}\)
所以\(f_i = (f_{i+1} + f_{i-1})p + (1 - 2p)f_i + \frac{i}{s}\)

\[2pf_i = (f_{i+1} + f_{i-1})p + \frac{i}{s} \]

\[2f_i = f_{i+1} + f_{i-1} + \frac{\frac{i}{s}}{p} \]

\(p = \frac{i(s-i)}{s(s-1)}\)

\[2f_i = f_{i+1} + f_{i-1} + \frac{\frac{i}{s}}{\frac{i(s-i)}{s(s-1)}} \]

\[2f_i = f_{i+1} + f_{i-1} + \frac{s-1}{s-i} \]

\(i=1\) 时,不需要考虑 \(f_0\)\(2f_1 = f_2 -1\)
显然的,\(f_s = 0\)

\[2f_i = f_{i+1} + f_{i-1} + \frac{s-1}{s-i} \]

\[f_i - f_{i+1} = f_{i-1} - f_i + \frac{s-1}{s-i} \]

\[f_{i+1} - f_i = f_i = f_{i-1} - \frac{s-1}{s-i} \]

\(f_1 = f_1 - f_s = \sum\limits_{i=2}^s f_i - f_{i-1}\)

\[=\sum\limits_{i=2}^s (f_1 - f_2) + \sum\limits_{j=2}^{i-1} \frac{s-1}{s-i} \]

\[= (s-1)(f_1-f_2) + \sum\limits_{i=2}^s\sum\limits_{j=2}^{i-1} \frac{s-1}{s-i} \]

\[=(s-1)(f_1-f_2) + \sum\limits_{j=2}^{s-1} \frac{s-1}{s-i} * (s-i) \]

\[=(s-1)(f_1-f_2) + \sum\limits_{j=2}^{s-1} (s-1) \]

\[=(s-1)(f_1-f_2) + (s-2)(s-1) \]

\(f_1 - f_2 = f_1 - (2 f_1 - 1) = 1 - f_1\)

\[f_1 = (s-1)(f_1-f_2) + (s-2)(s-1) \]

\[f_1 = (s-1)(1-f_1) + (s-2)(s-1) \]

\[f_1 = s-1 + (s-1)f_1 + (s-2)(s-1) \]

\[sf_1 = (s-1)^2 \]

\[f_1 = \frac{(s-1)^2}{s} \]

答案为 \(\sum\limits_{i=1}^n f_{a_i}\)
推到 \(max(a_i)\) 即可。

CF850F Rainbow Balls 题解

原文:https://www.cnblogs.com/zkyJuruo/p/13498253.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!