首页 > 其他分享 >[ABC176F] Brave CHAIN

[ABC176F] Brave CHAIN

时间:2023-10-24 15:13:57浏览次数:49  
标签:Brave CHAIN max 更新 ABC176F 枚举 le DP

[ABC176F] Brave CHAIN

洛谷:[ABC176F] Brave CHAIN

Atcoder:[ABC176F] Brave CHAIN

Problem

hhoppitree 有 \(3n\) 张卡片,其中每张卡片上都写着 \(1\sim n\) 中的一个数,他会重复以下操作 \(n-1\) 次:

  • 将最左侧的 \(5\) 张牌任意排列,排列后,删去最左侧的 \(3\) 张牌,如果这三张牌上写着同样的数,hhoppitree 可以获得 \(1\) 分。

最后,如果剩余的 \(3\) 张牌上的数字一样,那么他还可以额外得到 \(1\) 分。

现在,hhoppitree 想要知道,他得到的分数最高是多少。

\(1 \le N \le 2000\),\(1 \le A_{i} \le N\)。

Solution

有一个显然的 \(O(n^3)\) DP,记 \(f_{i, x, y}\) 表示进行了 \(i\) 次操作,剩余序列的左起第一个元素为 \(x\)、第二个元素为 \(y\) 的最大分数。之所以能这样记是因为第 \(i\) 次操作后被影响的是一段 确定 的前缀,即每次操作会影响到 \(3\) 个 确定 的元素,因此只需记录由之前操作剩下的 \(2\) 个元素即可知道当前操作需要执行的 \(5\) 个元素是什么。

由于枚举状态的时间复杂度就达到了 \(O(n^3)\),因此我们不能枚举所有状态。由于 \(f_{i, x, y}\) 对于 \((x, y)\) 关于 \(i\) 单调不降,因此可以考虑采取滚动数组转移,转移时只需枚举需要被更新的状态。

考虑给这个 DP 加上一些策略来优化它,比如这个贪心策略:如果当前操作的牌中存在三张相同数字的牌,那么直接打出计入分数。还是容易猜到的。

我们需要一个把策略套进 DP 转移中的方式。由于我们已经知道了每次操作中的其中 \(3\) 个数,我们可以根据这三个数的值去辅助 DP 转移,换句话说,我们可以用这三个确定的元素去 限制被更新的 DP 状态在一个可以接受的枚举范围内

下面开始转移。

考虑使用 “满三加一” 的策略:

  • 若三个数相同:\(f_{i, x, y} \xleftarrow{\max} f_{i - 1, x, y} + 1\)。由于不能枚举所有状态,因此这里可以将 \(+1\) 直接计入最终的答案,而 \(f_{i, x, y}\) 保持不变。

    注意:此时需要立即下一步操作,因为这里视作强行将这三张牌打出,不能进行其它操作。

  • 若两个数相同,记 \(p\) 为相同的数,\(q\) 为另一个,则:\(f_{i, x, q} / f_{i, q, x} \xleftarrow{\max} \max(f_{i - 1, p, x} + f_{i - 1, x, p}) + 1\)。枚举 \(x\),更新 \(O(n)\)。

  • 记这三个数分别为 \(p, q, r\),则:\(f_{i, q, r} / f_{i, r, q} \xleftarrow{\max} f_{i - 1, p, p} + 1\),对 \(q, r\) 也同理更新,\(O(1)\)。

    注意:该更新对存在两个数相同的情况也要进行!!!(问题在于对单独的那一个数进行处理)

考虑重排对 DP 值的影响。记三个数为 \(p, q, r\)。

  • 把之前剩下的两个数全部打出,则:\(f_{i, p, q} / f_{i, q, p} / f_{i, p, r} / f_{i, r, p} / f_{i, q, r} / f_{i, r, q} \xleftarrow{\max} \max\limits_{1 \le x, y \le n} (f_{i - 1, x, y}, f_{i - 1, y, x})\)。由于 \(\max\) 值可以随更新时动态维护,因此不用枚举 \(x, y\),仍然是 \(O(1)\) 更新。
  • 在剩下的两个数中保留一个,则:\(f_{i, x, p} / f_{i, p, x} / f_{i, x, q} / f_{i, q, x} / f_{i, x, r} / f_{i, r, x} \xleftarrow{\max} \max\limits_{1 \le y \le n}(f_{i - 1, x, y}, f_{i - 1, y, x})\)。同理,对每个 \(x\) 实时维护 \(\max\) 值,实现 \(O(n)\) 更新。
  • 将新来的三个数 \(p, q, r\) 全部打出,但这种情况已经被 “满三加一” 的讨论中考虑过了,因此避开了 \(O(n^2)\) 更新。

实现上,可以用 vector 存哪些状态在当轮被更新。

于是总时间复杂度为 \(O(n^2)\),令人感动。调得令人感动。code ABC176F

标签:Brave,CHAIN,max,更新,ABC176F,枚举,le,DP
From: https://www.cnblogs.com/Schucking-Sattin/p/17784826.html

相关文章

  • langchain中的LLM模型使用介绍
    简介构建在大语言模型基础上的应用通常有两种,第一种叫做textcompletion,也就是一问一答的模式,输入是text,输出也是text。这种模型下应用并不会记忆之前的问题内容,每一个问题都是最新的。通常用来做知识库。还有一种是类似聊天机器人这种会话模式,也叫Chatmodels。这种模式下输入是......
  • 基于LangChain的LLM应用开发3——记忆
    此情可待成追忆,只是当时已惘然。我们人类会有很多或美好或痛苦的回忆,有的回忆会渐渐模糊,有的回忆午夜梦醒,会浮上心头。然而现在的大语言模型都是没有记忆的,都是无状态的,大语言模型自身不会记住和你对话之间的历史消息。根本用不着“时时勤拂拭”,天然就是“本来无一物”。每一次的请......
  • 基于LangChain的LLM应用开发3——记忆
    此情可待成追忆,只是当时已惘然。我们人类会有很多或美好或痛苦的回忆,有的回忆会渐渐模糊,有的回忆午夜梦醒,会浮上心头。然而现在的大语言模型都是没有记忆的,都是无状态的,大语言模型自身不会记住和你对话之间的历史消息。根本用不着“时时勤拂拭”,天然就是“本来无一物”。每一次的......
  • langchain
    对超长文本进行总结假如我们想要用openaiapi对一个段文本进行总结,我们通常的做法就是直接发给api让他总结。但是如果文本超过了api最大的token限制就会报错。这时,我们一般会进行对文章进行分段,比如通过tiktoken计算并分割,然后将各段发送给api进行总结,最后将各段的总......
  • vscode交叉编译cmake工程,toolchains设置
    在VisualStudioCode中编译CMake项目时,使用自定义工具链(toolchains)可以很有用,特别是当你需要交叉编译或使用不同的编译器时。以下是在VisualStudioCode中使用自定义工具链的一般步骤,以aarch64的嵌入式为例:创建自定义工具链文件:首先,你需要创建一个包含有关你的自定义工具链......
  • struts2 result type=chain、dispatcher、redirect
    dispatcher:用于页面转发,页面跳转过程一直是同一个线程,Action中的数据一直保存在。redirect:可用于返回一个页面、一个action、链接到一个网址。缺点:redirect把一个http返回码(SUCCESS)以及返回的页面位置一起重新发给web服务器,容纳后由web服务器产生一个新的......
  • typescript: Chain of Responsibility Pattern
     /***ChainofResponsibilityPattern责任链是一种行为设计模式,允许你将请求沿着处理者链进行发送,直至其中一个处理者对其进行处理。*file:Chaints.ts*TheHandlerinterfacedeclaresamethodforbuildingthechainofhandlers.*Italsodeclaresameth......
  • click() 方法无法生效时 使用ActionChains
    背景知识1ActionChains库它的缩写来自于以下单词:Action(动作)和Chains(链)背景知识2ActionChains提供了更多灵活的鼠标和键盘操作选项,可以用于处理更复杂的场景,如果click()方法无法生效,可以尝试使用ActionChains来模拟点击事件。在使用Selenium时,存在一种情况是click()......
  • Langchain-Chatchat项目:1-整体介绍
      基于Langchain与ChatGLM等语言模型的本地知识库问答应用实现。项目中默认LLM模型改为THUDM/chatglm2-6b[2],默认Embedding模型改为moka-ai/m3e-base[3]。一.项目介绍1.实现原理  本项目实现原理如下图所示,过程包括加载文件->读取文本->文本分割->文本向量化->问句向量化->......
  • Langchain-Chatchat项目:1.1-ChatGLM2项目整体介绍
      ChatGLM2-6B是开源中英双语对话模型ChatGLM-6B的第2代版本,引入新的特性包括更长的上下文(基于FlashAttention技术,将基座模型的上下文长度由ChatGLM-6B的2K扩展到了32K,并在对话阶段使用8K的上下文长度训练);更高效的推理(基于Multi-QueryAttention技术,ChatGLM2-6B有更高效的推理......