Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「APIO2012」Dispatching - 左偏树

    给定一棵 n n 个点的有根树,每个点有两个属性 Ci C_i Li L_i ,现在你要指定一个点 R R ,并在 R R 的子树内选取若干点(可以选取 R R 自己),使得这些点的 Ci C_i 的和不超过 M M ,而一个选取方案的价值为选取人数 ×LR \times L_R ,求选取方案的最大价值。

    于  APIO, BZOJ, 左偏树, 数据结构 继续阅读

  2. 「APIO2010」特别行动队 - 斜率优化 DP

    一支部队由 n n 名预备役士兵组成,士兵从 1 1 n n 编号,要将他们拆分成若干特别行动队,同一队中队员的编号应该连续。

    士兵 i i 的初始战斗力为 xi x_i 一支特别行动队的初始战斗力 x x 为各士兵初始战斗力之和。一支特别行动队的战斗力会被修正为 x=Ax2+Bx+C x' = Ax ^ 2 + Bx + C ,其中 A A B B C C 已知,A<0 A < 0

    求出将所有士兵组成若干特别行动队的最大总战斗力。

    于  APIO, BZOJ, DP, 单调队列, 斜率优化 继续阅读

  3. 「APIO2009」抢掠计划 - 强连通分量

    城中的道路都是单向的。不同的道路由路口连接。在每个路口都设立了一个 ATM 取款机。酒吧也都设在路口,虽然并不是每个路口都设有酒吧。他将从市中心出发,沿着单向道路行驶,抢劫所有他途径的 ATM 机,最终他将在一个酒吧庆祝他的胜利。

    他获知了每个 ATM 机中可以掠取的现金数额。他希望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后,该 ATM 机里面就不会再有钱了。

    于  APIO, BZOJ, Bellman-Ford, DAG, Tarjan, 强连通分量, 最长路, 缩点 继续阅读