DP 小汇

SRM 679 FiringEmployees

有一个 n 个点的树, 每个点有点权 (点权可能为负), 求包含点 1 的最大权连通子图 (的权值和)。

入门树形 DP, 表示以 i 为根的子树 中包含结点 的最大权连通子图。

.

SRM 602 TypoCoderDiv1

  • 某人是一个乐于炸鱼的 OI 选手, 有一天他觉得自己的炸鱼水平还不够高超, 决定去算一个更优的炸鱼方案。
  • 假设某网站的 rating 系统是一个按固定 rating 分级的系统, 即 rating 大于 L 时是 div1 , 否则为 div2。某人一天打了 n 场比赛, 第 i 场的 rating 变化量为 , 即假设打之前的 rating 为 x , 赢了这场 rating 变为 , 输了这场 rating 变为 (以某人的实力当然是想赢就赢想输就输了)
  • 由于某人的目的是炸鱼, 所以当他打上 div1 以后他需要在下一场比赛立刻跌到 div2 (如果这场比赛不是最后一场的话)。为了表演高超的炸鱼技巧, 某人想最大化他在组别间横跳的次数。求最大的横跳次数。

定义 表示第 i 场比赛,rating 为 j 时最大横跳次数。

刷表法,通过判断第 i 场比赛是否上线来转移:

  • 赢了不上线,则转移到下一场比赛:
  • 赢了上线,则转移到 (如果第二次能下线就转移,否则只转移第一个)

SRM 698 RepeatString

又有坏掉的复读机破坏了队形, 现在复读机群员们要把这个队形修复。现在有一个字符串 , 你可以进行三种操作:

  • 在任意一个位置插入任意字符
  • 删除任意一个字符
  • 修改任意一个位置的字符

求最少的操作次数把 s 重新修改成 aa 的形式 (即一个字符串 a 重复两次)。

考虑将字符串分段匹配,枚举最终 之间的断点, 表示将 编辑成相同字符串的最小代价

[NOI2007]Cash

读《从 Cash 浅谈一类分治算法的应用》

初始时有 S 元人民币,N 天每天三个参数 . 表示 A 券价格,B 券价格,比例系数。第 i 天可以做这样的操作:

  1. 把 AB 券按比例 x 卖出, ,x 是实数。
  2. 用 x 元购入 AB 券,并要求买入的 AB 券比例为
  3. 每天可以进行多次操作。

问 N 天后最大收入。(可以是小数)注意这里的简化版题目描述与原题目稍有不同

把问题抽象一点,设一个三元组 分别表示人民币,AB 券的数量。对于第一个操作相当于

买入 AB 券相当于

显然我们的操作就是通过买卖券来最大化收入。因此贪心地考虑,每天我们一定要么全部卖出,要么全部买入。

分别表示第 i 天能获得的最大人民币、A 券、B 券数量(可以在当他兑换)

其中根据贪心策略可以得到

优化 DP

可以把这个方程写成线性函数形式。而这个方程中 m,x 都非单调(注意 x 是不单调的,因为 都有关,后三者是不单调的)对于这样的情况,相当于我们需要动态维护凸壳。

平衡树维护凸壳

简单说一下平衡树维护凸壳的过程。由于取 MAX,因此维护的是一个上凸壳。以点的横坐标作为键值。每次插入一个点的时侯,判断前驱后继的斜率关系。如果能插入,再分别考虑前驱后继的删除问题。这些可以用 Splay 或者 FHQ 做出来。总复杂度 .

分治优化 DP

平衡树的做法较复杂,实现起来难度高。DP 相当于是在用之前的决策更新当前的 DP 值。因此考虑这样一个过程:我们要求解 ,那么我们先求出 的 DP 值,然后来静态更新 的 DP 值。显然这是一个递归的过程。

针对本题,具体地说,我们求 DP 序列,那么就先计算前一半的 DP 值,然后构造前一半的凸壳,并将后一半的按斜率 m 排序。这样就能扫一遍静态更新 DP 值。左右两半递归进行这个过程。求凸壳也需要排序,因此可以递归完成后做归并排序。静态更新的复杂度是线性的,总复杂度就是 的。这样做的实现难度小,较为适合。


  转载请注明: Sshwy's Blog DP 小汇

 上一篇
Hexo 博客搭建 + Github 配置 + 域名配置 Hexo 博客搭建 + Github 配置 + 域名配置
摘要 Hexo 作为一款轻量级的静态博客博客框架,本身访问的速度很快,官网的主题也很多,美观又高效。然而在配置的过程中仍有一些棘手的地方,例如 Git 的使用,SSH 秘钥的生成,插件的使用等。本文将从一个相对细致的角度介绍 Hexo 搭建
2018.10.06
下一篇 
Vbox 代理全局 Vbox 代理全局
在 Deepin 下使用 shadowsocks?你会发现一个叫做 aec-128-gcm 的加密方法是不被支持的 于是,搭建 Vbox-Win7 虚拟机. 配置好 ss 后,在网络 -NAT 的高级选项中的端口转发: 配置一下主机域名
2018.10.04
  目录