首页 > 其他分享 >P3577 [POI2014] TUR-Tourism

P3577 [POI2014] TUR-Tourism

时间:2024-11-02 14:47:37浏览次数:1  
标签:状态 dep TUR 选择 欧拉 P3577 Tourism 节点 dp

P3577 [POI2014] TUR-Tourism

可能很多人看到这道题既可以从父亲更新到儿子,又可以从儿子更新到父亲的时候,很多人都跟我一样是这样的:

各种有问号的表情包-满头问号脸表情包图片大全20张_配图网

于是这里分享一下我的一种思考。


直径 \(\le 10\),可以先求出 DFS 生成森林,这样树高不超过 \(10\) 且没有横叉边,我们使返祖边是通过祖先限制后代,于是可以记录节点到根节点所有点的状态,共三种:

  • \(0\):这个点选择了

  • \(1\):这个点没选择且相邻点没有选择(没被覆盖)

  • \(2\):这个点没选择且相邻点有选择(被覆盖)

首先求出这个树的欧拉序,下文中 \(x_i\) 表示欧拉序第 \(i\) 个位置的节点编号。

令 \(f_{i,j}\) 表示考虑欧拉序前 \(i\) 个位置,\(x_i\) 到根的路径上的状态为 \(j\) 时的最小代价。由于一个节点需要受到其祖先节点状态的限制,所以每个节点的决策(选或不选)应该在其欧拉序中第一个位置进行。
考虑 \(i-1\to i\) 的一次转移,假设之前的状态为 \(s=j\)。

  • 如果 \(x_{i-1}=fa_{x_i}\) 也就是说这是一条向下的边,考虑 \(x\)的的决策:

    • 如果 \(x_i\) 选择,那么当前节点的状态无论如何都是 \(0\),考虑与 \(x_i\) 有边的一个祖先 \(z\):

      • 如果 \(z\) 的状态为 \(0,2\),则 \(s\) 不作改变。

      • 如果 \(z\) 的状态为 \(1\),则 \(s\to s+2\times 3^{dep_z}\)。

    • 如果 \(x_i\) 不选择,那么看当前节点有没有被自己的祖先覆盖:

      • 如果没覆盖,则 \(s\to s+3^{dep_{x_i}}\)。

      • 如果被覆盖,则 \(s\to s+2\times 3^{dep}\)。

    最后让 \(dp_{i,s}\leftarrow dp_{i-1,j}\)。

  • 如果 \(fa_{x_{i-1}}=x_i\),也就是说这是一条向上的边,直接 \(dp_{i,j}=\min\{dp_{i-1,j},dp_{i-1,j+2\times 3^{dep_{x_{i-1}}}}\}\)。

最后一棵树的答案就是 \(\min\{dp_{2n-1,0},dp_{2n-1,2}\}\),最终答案就是所有树的答案之和。


其实我们没有必要真正的把欧拉序列求出来,直接在 DFS 遍历的过程中求一下就行了,复杂度 \(\mathcal O(3^hm)\),但是很多状态是不必要的,卡卡常就过了。

标签:状态,dep,TUR,选择,欧拉,P3577,Tourism,节点,dp
From: https://www.cnblogs.com/lupengheyyds/p/18521932

相关文章

  • Capture and Preserve Charts
    CaptureandPreserveChartsTransformchartsintostaticimagesforeffectivecommunicationanddatasharingacrossplatformsanddevices.Chartcomponentswithimageexportfeaturesempoweruserstosaveachart'svisualrepresentationasas......
  • ITS66204 Discrete Structures
    DiscreteStructures(ITS66204)Group Assignment (Weightage:30%)Case Study Title:Due Date: Sunday,01December 2024 (Week 11), 11:59 PMGroup Assignment(30%)MLO2: Demonstratefindingsandinsightsderivedfromapplicationsofdiscretestructu......
  • [超级硬件混响插件]TEGELER Audio Manufaktur RaumMaschine v1.1.8 [MacOSX, WiN](45.9
    Tegeler推出了一款混响效果器:Raummaschine,结合了高质量的DSP引擎和模拟管路,提供出色的声音和灵活性。Raummaschine是基于其硬件设计而创造的。这款独特的混响单元结合了高质量的DSP引擎、模拟管路和每个通道上的两个双三极管,以及输入和输出变压器。通过模拟硬件版本的每个方面......
  • 论文阅读Nature:Detecting hallucinations in large language models using semantic e
    论文阅读-Nature:Detectinghallucinationsinlargelanguagemodelsusingsemanticentropy(使用语义熵来检测大模型中的幻觉)作者:SebastianFarquhar,JannikKossen,LorenzKuhn&YarinGal单位:牛津大学,计算机科学学院,OATML实验室期刊:Nature时间线:2023年7月提交→......
  • 【java】什么是 Future 和 CompletableFuture - 一篇文章快速入门 Java 异步编程
    1.引言在现代Java编程中,异步编程变得越来越重要。随着多核处理器的普及,充分利用多线程可以大大提高程序性能和用户体验。在这种情况下,Future和CompletableFuture成为处理异步任务的核心工具。2.Future是什么?Future的定义及基本概念Future是Java并发库中的接口......
  • [水一篇] Structured Text(ST)
    StructuredText(ST),aprogramminglanguageusedinProgrammableLogicControllers(PLCs).StructuredTextisahigh-levellanguagethat'swidelyusedinindustrialautomationandcontrolsystems.It'satext-basedlanguagethatallowsprogramm......
  • IT界的大神-001-阿兰·图灵 (Alan Turing)
    -生平简介:阿兰·图灵,1912年6月23日出生于英国伦敦,是计算机科学和人工智能领域的先驱,被誉为计算机科学之父、人工智能之父。图灵在16岁时就能读懂爱因斯坦的著作,展现出过人的数学和科学天赋。-突出贡献及事迹:阿兰·图灵(AlanTuring)是20世纪最伟大的数学家和计算机科学家之......
  • macOS Ventura 13.7.1 (22H221) Boot ISO 原版可引导镜像下载
    macOSVentura13.7.1(22H221)BootISO原版可引导镜像下载2024年10月28日,Apple智能今日登陆iPhone、iPad和Mac。用户现可借助Apple智能优化写作,为通知、邮件和消息生成摘要,体验交互更自然、功能更丰富的Siri,使用消除工具移除图像中令人分心的物体,并体验更多功能。......
  • macOS Ventura 13.7.1 (22H221) 正式版发布,ISO、IPSW、PKG 下载
    macOSVentura13.7.1(22H221)正式版发布,ISO、IPSW、PKG下载2024年10月28日,Apple智能今日登陆iPhone、iPad和Mac。用户现可借助Apple智能优化写作,为通知、邮件和消息生成摘要,体验交互更自然、功能更丰富的Siri,使用消除工具移除图像中令人分心的物体,并体验更多功能......
  • Nature 正刊丨空间蛋白质组学确定JAKi是一种致命皮肤病的治疗方法
    01摘要中毒性表皮坏死松解症(TEN)是一种由常见药物引发的致命药物性皮肤反应,是一个新出现的公共卫生问题1,2,3。TEN患者会因角质形成细胞死亡而发生严重和突然的表皮脱离。尽管已经提出了驱动角质形成细胞死亡的分子机制,但主要驱动因素仍然未知,TEN4,5,6没有有效的治疗方法。在......