首页 > 其他分享 >对于 CF1107E 中 dp 状态设计的一点想法

对于 CF1107E 中 dp 状态设计的一点想法

时间:2024-05-02 17:33:51浏览次数:22  
标签:删掉 题解 位置 保留 想法 区间 CF1107E dp

不太想发到洛谷讨论区,就往这里放了。

我觉得现有的题解都没说明白为什么本题的状态和转移能覆盖所有情况,并且感觉也非常不自然,没见过的话感觉挺难发现这么一个东西。

然而这个 dp 其实是可以自然地推导出来的。

首先发现这个过程非常难以描述,主要原因在于很难刻画一个局面。然而,如果知道一个局面是什么样的,转移是简单的。

因此我们考虑 时光倒流,直接考虑最后一次操作,这时的局面非常简单:一定是删掉全部的数。

然后考虑这次操作在原序列上的表现:选定若干个字符相等的位置 \(s_1,s_2,\dots,s_k\),分割出来若干段形如 \((s_i,s_{i+1})\) 这样的区间,因为我们是倒着操作的,所以这些分割出来的区间不会再有交集,直接做下去就好了。

为了转移,我们定义辅助数组 \(g(l,r,k)\):表示我们选了 \(k\) 个位置留作最后操作的最大价值。转移并不困难,然后再得到 \(f(l,r)\) 即可。

发现这个东西其实和 [THUSC 2016] 成绩单 描述的 dp 是很类似的。

回过头来看一看我们干了一件什么事,因为删掉 \((s_i,s_{i+1})\) 这样的区间的顺序并不重要,我们可以这样从右往左考虑这个过程:

  • 保留一个位置,并删掉和前一个保留的位置之间的区间。要求保留的位置上的字符相同。

这个 保留的位置 就是 luogu 题解里面的 \(f(l,r,k)\) 中 \(k\) 的含义,当然也有一点不同:允许过程中把这个 \(k\) 清空。

直接正着想的话可能也能感受到这个过程,但毕竟不怎么自然啊。

所以这种过程性较强的题目,从最终局面出发始终可以作为一种选择。

标签:删掉,题解,位置,保留,想法,区间,CF1107E,dp
From: https://www.cnblogs.com/663B/p/18170360

相关文章

  • python3使用dpkt生成PCMA格式rtp流
    操作系统:CentOS7.6_x64Python版本:3.9.12dpkt版本:1.9.8PCMA编码是VoIP通信中常见的格式,今天整理下CentOS7环境下,python3如何使用dpkt生成PCMA格式rtp流的笔记,并提供相关示例代码、运行效果视频和配套文件下载。我将从以下几方面进行展开:背景材料使用dpkt生成PCMA格式rt......
  • m基于CCSDS标准的LDPC编码器的FPGA实现,包含testbench,码长1024,码率0.5
    1.算法仿真效果vivado2019.2仿真结果如下:   2.算法涉及理论知识概要      LDPC码是一种具有稀疏校验矩阵的线性分组码,由RobertG.Gallager在1962年首次提出。它利用图论中的Tanner图来表示其编解码结构,其中节点分为变量节点和校验节点。变量节点对应于消息比特......
  • 【DP】买卖股票的最佳时机III
    题源-之前都是数组存,然后转移状态,这次是直接四个变量,非常神奇-在该问题中,定义了五种状态,分别是:未进行过任何操作、只进行过一次买操作、进行了一次买操作和一次卖操作(完成了一笔交易)、在完成了一笔交易的前提下进行了第二次买操作以及完成了全部两笔交易。-然后,通过状态转移方......
  • 关于游戏付费的一点想法
    最近被问到,为什么玩原神只花了1000多块钱,我被问住了,不知该作何反应。这里打算重新整理一下思路,尝试回答。首先谈谈钱,对于一般打工人来说,金钱是劳动的凭证,我们可以用它来兑换其他人的劳动成果。在买断制、点卡制游戏中,金钱体现了这种性质:我们用自己工作赚来的钱付费,换取运行游戏的......
  • sub-1G低功耗soc芯片DP32RF002
    DP32RF002是深圳市动能世纪科技有限公司研制的基于ARMCortex-M0+内核的超低功耗、高性能的、单片集成(G)FSK/OOK无线收发机的32位SoC芯片。工作于200~960MHz范围内,支持灵活可设的数据包格式,支持自动应答和自动重发功能,支持跳频操作,支持FEC功能,同时内部集成了完整的......
  • 【DP】编辑距离
    https://leetcode.cn/problems/edit-distance/description/?envType=study-plan-v2&envId=top-interview-150非常难的一种考虑方式【转载】dp[i][j]代表将word1的前i个字符转换为word2的前j个字符所需的最少步数。因此,根据题目给出的状态转移方程:当word1[i]==wor......
  • Rockchip RK3399 - DRM eDP调试
    ----------------------------------------------------------------------------------------------------------------------------开发板:NanoPC-T4开发板eMMC:16GBLPDDR3:4GB显示屏:15.6英寸HDMI接口显示屏u-boot:2023.04linux:6.3----------------------------------......
  • BZOJ5424 烧桥计划(单调队列优化dp)
    传送门(vjudge)解题思路注意到\(a_i\)的范围很小,是1000~2000之间,于是我们可以直观感受到k一定不会特别大,推一下可以得出k最多大概在四五百左右,于是可以直接考虑dp[i][j]为前i个数里面选了j个分割点,且第i个数是分割点的最小代价。转移要分两种情况讨论:sum[pre+1~i......
  • oracle数据导入导出,备份还原命令expdp&impdp(只导出元数据,不导出表数据,最全,最完善的步
    感谢金龙鱼先生分享,原文来自https://blog.csdn.net/kou869929526/article/details/125791113一,编码要求以及数据库版本要求检查数据库版本(用于决定导出时生成为哪个版本的dmp头文件)selectversionfromv$instance;检查字符集是否一致(字符集不一致,不能导入)selectuserenv(......
  • Surface Pro 4 miniDP转接HDMI 4K显示的问题
    1、我在某东上买了一个支持4k的minidp转hdmi的转接头,可以支持2K显示器。不过直接连接的话2K显示器最高只能设置1080P的分辨率。解决方法:可以先单独让2k显示器显示,设置分辨率为2k,然后再扩展显示,就可以完美使用了,希望有帮助。2、SurfacePro4及其扩展坞上的MiniDisplayPort能否......