首页 > 其他分享 >atcoder DP做题笔记

atcoder DP做题笔记

时间:2024-11-09 16:07:47浏览次数:3  
标签:atcoder 色子 题意 度为 胜率 做题 DP dp

[ABC163E] Active Infants

题意:给定长度为 \(n(n \le 2 \times 10^3)\) 的序列 \(a\) ,重排使得 \(a_x \times |x-p_x|\) 之和最大。
独立完成。
从大到小地考虑 \(a_i\) ,贪心地使得 \(|x-p_x|\) 最大。那么 \(p_x\) 要么在最左,要么在最右。因此在左边和右边形成了一坨前/后缀,然后就能转移了。

[ABC282G] Similar Permutation

题意:定义两个排列 \(A,B\) 的相似度为满足 \((A_{i+1}-A_i)(B_{i+1}-B_i)>0\) 的 \(i\) 的个数。求有多少对长度为 \(n\) 的排列相似度为 \(K\)。
独立完成。
首先有弱化版 AT_dp_t 。具体做法是考虑最后一个数在前缀的相对位置,往里插就行了,与这道题无本质区别。直接枚举 \(A\) 和\(B\) 的最后一个符号是 \(>\) 还是 \(<\) 。然后记录当前相似度、\(A,B\)排列的最后一位在前缀中的相对位置就做完了。

[ABC281G] Farthest City

题意:构造 \(n\) 个点的图,使得 \(1\) 到 \(n\) 的距离严格大于 \(1\) 到其他点的距离。
独立完成。
直接根据 \(1\) 到该点的距离分层。层内随便连,层之间右边的每个点至少连一条边。随便转移一下就行了。

[ABC342F] Black Jack

题意:你和另一个人投 \(D\) 面的骰子。那个人一直摇色子直到大于等于 \(L\)。你可以任意时刻停止。求最右策略下获胜概率 \(x<=n \space and \space (y>x \space or \space x>y)\)
基本独立完成。
考虑 \(dp\) 。首先另一个人的方式与你无关,直接 \(dp\) 中最后在 \(i\) 的概率。然后到了一个位置 \(i\) 决策是否再摇色子会更优,也就是新跳到格子的期望胜率是否比当前胜率大。随便做一下就完事了。本来我在后面一次 \(dp\) 是顺序,然后期望胜率直接用第一次 \(dp\) 值算,但这样是不准确的,会 \(WA\) 掉3个点。因此应该倒着 \(dp\)。

标签:atcoder,色子,题意,度为,胜率,做题,DP,dp
From: https://www.cnblogs.com/IANYE/p/18522582

相关文章

  • CF1647D Madoka and the Best School in Russia 做题记录
    我不会分讨。可以知道一个美丽数\(a\)的充要条件是\(a=d\timesk\)且\(d\nmidk\)。有个朴素的想法是将给你的\(x\)拆成\(d^p\timesk\)。显然如果\(p\le1\)那么我们拆不动。如果\(k\)可以拆成大于\(2\)个数的乘积,那么是可行的。如果\(k\)是质数,那么我们就......
  • 空夜 [换根DP]
    空夜Description给定\(n\)个节点的树,每个点有点权\(a_i\),对于每个\(i\),求出\(\sum_{j}\lfloor\frac{a_i}{2^{dis(i,j)}}\rfloor\)。\(dis(i,j)\)表示\(i\)到\(j\)的树上最短路径。Solution对于每个\(i\)都要求答案,等价于求以\(i\)为根的树的答案,可以想到......
  • 洛谷 P11268 【MX-S5-T2】买东西题 做题记录
    我不会贪心。\(a\)元的物品有\(b\)元的折扣,就相当于\(a\)元的物品有一张\(a-b\)元的优惠券。因为一张优惠券是满\(w\)元才可以用,所以可以用的物品在价格\(a\)上是一段区间\([a,\inf]\)。有一个很朴素的想法是,将每一个物品最多能省多少钱先弄出来,然后用优惠券想办法......
  • RLGF无人机深度强化学习任务的通用训练框架(SAC, DQN, DDQN, PPO, Dueling DQN, DDPG)
    RLGF是一个通用的训练框架,适用于无人机的深度强化学习任务。该框架集成了多种主流的深度强化学习算法,包括SAC(SoftActor-Critic)、DQN(DeepQ-Network)、DDQN(DoubleDeepQ-Network)、PPO(ProximalPolicyOptimization)、DuelingDQN(决斗深度Q网络)以及DDPG(DeepDeterministicPo......
  • Android13 修改设备的density(dpi)
    DPIDPI,全称DotsPerInch,是一个衡量屏幕密度的关键指标。其中,Inch(英寸)作为物理单位,在任何设备上的大小都是恒定不变的。因此,DPI具体指的是在一英寸的物理长度内所能容纳的像素点(Dot)数量。例如,160DPI的屏幕意味着在一英寸的长度内包含160个像素点,而320DPI的屏幕则表明一英寸......
  • Air780E软件指南:UDP应用示例
    一、UDP概述UDP(用户数据报协议,UserDatagramProtocol)是一种无连接的、不可靠的传输层协议,主要用于实现网络中的快速通讯。以下是UDP通讯的主要特点:1.1无连接通讯:UDP在发送数据之前不需要建立连接,这大大减少了通讯的延迟。发送方只需将数据包封装成UDP报文,并附上目的地址......
  • 网络编程(一):UDP socket api => DatagramSocket & DatagramPacket
    目录1.TCP和UDP1.1TCP/UDP的区别1.1.1有连接vs无连接 1.1.2可靠传输vs不可靠传输 1.1.3面向字节流vs面向数据报1.1.4全双工vs半双工2.UDPsocketapi2.1DatagramSocket2.1.1构造方法2.1.2receive/send/close2.2DatagramPacket2.2.1......
  • 换根 DP
    树形DP中的换根DP问题又被称为二次扫描,通常需要求以每个点为根时某个式子的答案。这一类问题通常需要遍历两次树,第一次遍历先求出以某个点(如\(1\))为根时的答案,在第二次遍历时考虑由根为\(u\)转化为根为\(v\)时答案的变化(换根)。这个变化往往分为两部分,\(v\)子树外的点到......
  • 第一天打卡,udp协议
    今天学了udp协议基础,udp协议是一种无连接的网络协议,提供一种简单的方式来输送数据。发送:要用到的方法封装在InetAddress类中,其中DatagramSocket对象ds相当于快递员身份,不传递参数值的话会随机生成端口,进行输送快递(数据),快递的身份由DatagrampPacket对象充当,把东西打包。其中的......
  • AtCoder Beginner Contest 358 - VP记录
    Preface这次的动规题真的多,起码有三道都是。赛时做完ABCD以后就去攻G去了,可惜犯了煞笔错误搞WA了。赛后补F的时候思路代码啥的都挺顺的(没看题解独立切的蓝题),就是犯了更煞笔的错误,成消愁......