首页 > 其他分享 >CF1866M Mighty Rock Tower 题解

CF1866M Mighty Rock Tower 题解

时间:2023-11-03 19:22:21浏览次数:46  
标签:题解 CF1866M times Mighty Rock Tower sum dp

Problem - 1866M - Codeforces

Mighty Rock Tower - 洛谷

  • 先考虑一个 \(O(n^2)\) 的 dp

    • 设计状态: \(dp_i\) 表示搭 \(i\) 层的期望

    • 转移:\(dp_i=dp_{i-1}\times(1-P_i)+\sum\limits_{j=i}^{n-1}dp_j\times P_{j+1}^{j-i+1} \times (1-P_{j+1})\) ,显然是有后效性的,但我们展开 \(dp_{n}\) ,移一下项,就变成了之和 \(dp_{n-1}\) 有关的了,就这样一直展开到 \(dp_0\) 再递推回去,就可以做到 \(O(n^2)\)

  • 考虑优化,我们的复杂度主要在哪?主要是在后面部分的展开,换言之我们并不好考虑从高层掉到第 \(i\) 层的情况,因此我们不妨考虑强制从 \(i-1 \rightarrow i\) 的期望

    • 设计状态: \(dp_i\) 表示从 \(i-1 \rightarrow i\) 的期望次数

    • 转移:

    • \[\begin{align} dp_i &=1+\sum_{j=1}^{i}dp_j\times P_i^i + \sum_{j=1}^{i-1} P_i^j \times (1-P_i) \times \sum_{k=i-j+1}^{i} dp_k \\ &=1+\sum_{j=1}^{i}dp_j\times P_i^i + \sum_{k=1}^{i} \sum_{j=i-k+1}^{i-1} P_i^j \times (1-P_i) \times dp_k \\ &=1+\sum_{j=1}^{i}dp_j\times P_i^i + \sum_{k=1}^{i} \sum_{j=i-k+1}^{i-1} P_i^j \times (1-P_i) \times dp_k \\ &=1+\sum_{j=1}^{i}dp_j\times P_i^i + \sum_{k=1}^{i} (P_i^{i-k+1}-P_i^i)\times dp_k \\ &=1+\sum_{j=1}^{i}dp_j\times P_i^{i-j+1}\\ (1-P_i)dp_i &=1+\sum_{j=1}^{i-1} dp_j\times P_i^{i-k+1}\\ dp_i &=\frac{1+\sum_{j=1}^{i-1} dp_j\times P_i^{i-k+1}}{i-P_i} \end{align} \]

    • 优化转移:发现 \(P_i\) 的原因并不好优化,但原题 \(P_i \leq 99\) ,因此我们可以直接对每一种 \(P_i\) 都做一遍前缀和,最终复杂度 \(O(n \Sigma)\)

标签:题解,CF1866M,times,Mighty,Rock,Tower,sum,dp
From: https://www.cnblogs.com/fox-konata/p/17808241.html

相关文章

  • [ARC104E] Random LIS 题解
    题意给定一个长度为\(N\)的序列\(A\),按照下列方式生成一个长度为\(N\)的序列\(X\):\(\foralli\in[1,n]\),\(X_i\)在\([1,A_i]\)中的整数中均匀随机生成。求其最长上升子序列长度的期望,对\(10^9+7\)取模。\(1\leN\le6,1\leA_i\le10^9\)。题解由于\(N\)......
  • CSP-S2023 全场题解
    lock这题就是个模拟吧,赛时被迷惑了以为是什么不可做题,仔细看只有\(10^5\)种状态,那就枚举好了。我们分别从状态串出发,枚举它能达到的答案,加到set取个并集,不过注意给定的状态不能是密码,要减掉。注意不要直接计数器减减,不然如果有相同的算在状态里面的会多减,我考场代码就这么被......
  • NOIP 提高组 题解
    NOIST2023涂色游戏对于每一行每一列记录一个时间戳,对于每个格子颜色即为时间戳较大的颜色。幂次考虑暴力,我们发现\(O(\sqrt[3]{n})\)的复杂度是可以接受的,所以可以枚举\(\sqrt[3]{n}\)内的数然后暴力往上乘,可以用一个unordered_map判重,时间复杂度大概为\(O(\sqrt[3]{n}......
  • 【POJ 1731】Orders 题解(全排列)
    描述商店经理按照标签的字母顺序对各种商品进行了分类。所有标签以同一字母开头的种类都存放在标有该字母的同一仓库(即在同一建筑物内)。在白天,商店经理接收并预订要从商店发货的货物订单。每个订单只需要一种货物。商店经理按照预订的顺序处理请求。你事先知道今天商店经理必须处......
  • flask部署在腾讯云上,但在本地使用网页无法访问——问题解决
    flask部署在腾讯云上,但在本地使用网页无法访问——问题解决1.修改腾讯云防火墙,把对应的port开放:2.修改代码if__name__=='__main__':app.run(host="0.0.0.0",port=5000,debug=True)参考链接:https://zhuanlan.zhihu.com/p/611969276......
  • HCIP Datacom H12-831考题解析
    OSPFv3专题6.关于0SPFv3报文,以下哪个描述是正确的?郑锦程校对整理2023.11.03A.OSPFv3的Hello报文携带了路由器所有接口的IPv6地址B.OSPFv3使用链路本地地址作为发送报文的源地址,报文可以被转发到始发链路范围之外C.OSPFv3使用IPv6组播地址FF02:1和FF02:2发送OSPFv3报文D.可以在OSPFv......
  • 【真题解析】软件工程-重点题目解析(1)
    截止2023年4月本系列是我自己在学习过程中记录的资料;因为内容比较格式比较多样;用markdown靠记录非常浪费时间;再加上对时效性的考虑;就以PPT的形式记录了;本系列因为是自己的理解为主,因此,难免与教材中的内容有误差,主要是从自己的知识角度解释题目的答案,个人感觉是有助于记忆的。如果有......
  • 苏格拉底问答、实践过程截图、遇到问题解决问题截图,代码链接
    #include<signal.h>#include<stdio.h>#include<sys/time.h>intcount=0;structitimervalt;voidtimer_handler(intsig){printf("timer_handler:signal=%dcount=%d\n",sig,++count);if(count>=8){printf("cancel......
  • [ARC104B] DNA Sequence 题解
    题意对于一个只含有A,C,T,G的字符串\(s\),定义其为匹配的当且仅当其中A的数量和T的数量相等,C的数量和G的数量相等。给定一个长度为\(N\)的字符串\(S\),求其有多少个非空子串是匹配的。\(1\leN\le5000\)。题解\(\mathcal{O}(N)\)做法。首先考虑如果字符集只有......
  • [ARC104D] Multiset Mean 题解
    题意给定\(N,K\)和\(M\)。对于每个大小在\([1,N]\)中的\(x\),求每个元素大小在\([1,N]\)中,平均数为\(x\)且相同元素不超过\(K\)个的可重集的数量,对\(M\)取模。\(1\leN,K\le100\),\(M\)为质数。题解发现对于\(x\),若存在一个合法的集合\(S\),那么有\[\sum\li......