轻功

题目描述

一共有 n 个木桩,要求从起点(0)开始,经过所有梅花桩,恰好到达终点 n,尊者神高达一共会 k 种门派的轻功,不同门派的轻功经过的梅花桩数不同,花费时间也不同。但是尊者神高达一次只能使用一种轻功,当他使用别的门派的轻功时,需要花费 W 秒切换(开始时可以是任意门派,不需要更换时间)。由于尊者神高达手残,所以经过某些梅花桩(包括起点和终点)时他不能使用一些门派的轻功。尊者神高达想知道他最快多久能到达终点。如果无解,则输出-1。

思路

我们可以写一个 $O(nk)$ 的 DP。$f_{i,j}$ 表示经过第 $i$ 个梅花桩结束使用门派 $j$,那么它可以从 $f_{i-cost_j,p}$ 转移过来。发现 $p$ 的具体数值对转移没有影响,只需要特判 $p==j$ 的情况,所以处理 $f_{i,p}$ 的最小值,O(1) 转移。限制条件只需要前缀和判断即可。

代码

开荒

题目描述

(太长了以下是我的精简版)

给定一棵树,点有权值,支持修改。询问某 $k$ 个点的最小联通块权值和。

思路

首先我们不考虑修改,如何计算答案。发现将 $k$ 个点按 $DFS$ 序升序以后,点 $i$ 到自己和前一个点 $i-1$ 的最近公共祖先深度一定递增,并且到 $LCA$ 的路径的集合就是最小联通块,注意第一个点要和所有点的 $LCA$ 相连。将点权转移到连接父亲的边上,计算答案的时候可以做到不重复,但是会遗漏所有点的 $LCA$,单独计入即可。

代码

跑商

题目描述

给定一个 $n$ 个点,$m$ 条边的简单无向图,支持修改点权。每次询问路径上点权最小值。

思路与代码

CodeForces 487E

  1. oyyj603470138
    Nov 15, 2018

    您想必500+稳了(我又炸了,才430+)

    Reply
    • xgzepto
      Nov 16, 2018

      我 430 都没有的。。。

      Reply