DP 優化小技巧
  • 2022 年 10 月 5 日
  • 筆記

收录一些比较冷门的 DP 优化方法。 1. 树上依赖性背包 树上依赖性背包形如在树上选出若干个物品做背包问题，满足这些物品连通。由于 01 背包，多重背包和完全背包均可以在 \(\mathcal{O}(V)\) 的时间内加入一个物品， \(\mathcal{O}(V ^ 2)\) 的时间内合并两个背 …

Continue Reading

[NOI2005] 聰聰與可可
  • 2022 年 9 月 11 日
  • 筆記

NOI 2005 聪聪与可可 机器猫の传送门 期望DP+记搜 聪聪一直在向可可方向追，所以不会回到原处，不具有后效性，考虑用概率与期望DP+记忆化搜索求解 用dp[x][y]表示可可在x点,聪聪在y点时步数的期望值 判断边界 ①当x==y时结束 （此时毫无疑问的，dp[x][y]=0） ②当x!=y …

Continue Reading

DP 優化方法合集

0. 前言 写完 这篇文章 后发现自己对于 DP 的优化一窍不通，所以补了补 DP 的一些优化，写篇 blog 总结一下。 1. 单调队列/单调栈优化 1.2 算法介绍 这应该算是最基础的 DP 优化方法了。 顾名思义，单调队列/单调栈优化 DP 就是保持容器内元素的单调性，以达成减少冗余状态的目的 …

Continue Reading

關於01背包個人的一些理解

01背包 01背包题目 思路剖析 1.当我们第一次看到题目的时候，很容易想到运用贪心的思想，每次拿性价比最大的物品。 容易举出反例： 3 7 6 10 //1.666... 5 8 // 1.6 2 3 //1.5 2.接着我们很自然的就可以想到，既然运用贪心的思想不行，那么就枚举所有选取物品的情况 …

Continue Reading

AcWing 1220. 生命之樹

题目链接 题目描述： 在X森林里，上帝创建了生命之树。 他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。 上帝要在这棵树内选出一个非空节点集 S，使得对于 S 中的任意两个点 a,b，都存在一个点列 {a,v1,v2,…,vk,b} 使得这个点列中的每个点都是 S …

Continue Reading

AcWing 1222. 密碼脫落

题目链接 题目描述： X星球的考古学家发现了一批古代留下来的密码。 这些密码是由A、B、C、D 四种植物的种子串成的序列。 仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。 由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。 你的任务是： 给定一个现在看到的密码串，计 …

Continue Reading

AcWing 1047. 糖果

题目链接 题目描述： 由于在维护世界和平的事务中做出巨大贡献，Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。 在这一天，Dzx可以从糖果公司的 N 件产品中任意选择若干件带回家享用。 糖果公司的 N 件产品每件都包含数量不同的糖果。 Dzx希望他选择的产品包含的糖果总数是 K 的 …

Continue Reading

AcWing 1050. 鳴人的影分身

题目链接 题目描述： 在火影忍者的世界里，令敌人捉摸不透是非常关键的。 我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。 影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。 针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有 …

Continue Reading

CF908G&LOJ6697口胡
  • 2022 年 3 月 17 日
  • 筆記

为什么我从ACAM做到了数位DP啊 考虑枚举前缀顶着最高位和后缀没有顶着的最高位。 考虑计算一个数对答案的贡献。统计 \(t\) 的出现次数记录到 \(c[t]\) 中。 贡献就是 \(\sum_{i=0}^{9}((\sum_{x=0}^{\sum_{j=i}^{9}c[j]-1}i\times1 …

Continue Reading

背包九講--混合背包和分組背包問題

混合背包顾名思义是讲0/1，多重和完全背包混合起来的背包问题，我们处理这种背包问题一般是进行条件判断处理然后在进行三个背包问题分析就可以了。 实战项目：//www.acwing.com/problem/content/description/7/ //www.luogu.com.cn/problem …

Continue Reading

VirMach 便宜 VPS