Team Building *2300

首先可以想到暴力 dp。

设 $f_{i,j,S}$ 表示前 $i$ 个人，选了 $j$ 个观众，队伍的选择状态为 $S$。

复杂度是炸的。

但仔细想想，我们真的要记这么多状态吗？

如果你把这道题想成一个普通的背包，那就错了，因为这题很特殊。

每个物品的体积都是 1。

这说明此时贪心是正确的。

我们按观众值降序排序，那么对于观众值而言，一定是全选前面的更优。

设 $f_{i,S}$ 表示前 $i$ 个人，队伍的选择状态为 $S$，$num_S$ 为 $S$ 里 $1$ 的个数。

转移时，如果当前观众人数小于 $k$，那么一定是让他当观众最优。

因为观众是能选就选的，所以观众人数很容易得出，就是 $i-num_S$。

复杂度 $O(n2^p)$

Minimal Labels *2300

第一眼看到以后以为是拓扑板子，直到看到第三个样例。

经过手玩可以发现，我们应该每次都先填未填的点里编号最小的点，这样才能让字典序更小。

但是编号最小的点可能被一些点指向，所以要先把前面的那些点给填上。

前面那些点又构成一张新图，这就是一个子问题了，递归解决即可。

找前面点可以建反图往回跑即可。

复杂度？

然而正解是建反图后拓扑，然后倒序编号。

我们刚才的思路都是正着来的，那为什么倒着才是对的呢？

正解是对的比较好理解，但感性理解一下，我们的做法似乎和倒着做是一样的？

Trains and Statistic *2300

类似 Floyd，对于两个点，我们要么一步到，要么找一个中转点。

而这道题不需要 $O(n^3)$ 的原因是：每个点能到的区间是一定的。

所以我们可以贪心。

既然一步走不到，那肯定走的越远越好。

所以我们一定会从 $i$ 走到 $[i+1,a_i]$ 里 $a$ 最大点 $j$。

设 $f_i=\sum_{j=i+1}^n p_{i,j}$。

那么 $f_i$ 只会从 $f_j$ 转移来。

转移为

$$f_i=f_j+n+j-a_i-i$$

首先让编号 $>j$ 的点强制从 $j$ 转移过去，那么这部分答案是 $f_j+n-j$。

这会把 $[j+1,a_i]$ 里的点多算一步，那么减去 $a_i-(j+1)+1$。

最后加上 $[i+1,j]$ 的点，他们只需要走一步，是 $j-(i+1)+1$。

合起来就是 $f_j+n+j-a_i-i$。

求 $j$ 是一个 RMQ 问题，随便做。

复杂度 $O(n\log n)$

Monster Invaders *2300

又读错题。

贪心肯定是很难贪的。考虑 dp。

但是 dp 是不是有后效性？毕竟可以从前面过来，还可以从后面过来。

难道要高斯消元解方程组？复杂度也接受不了啊。

但你仔细想想，我们真的会从很后面的地方过来吗？

显然不会。

如果我们现在在 $i$，剩个 boss 差一血没打死，然后被强制移到了 $i+1$。

假设我们一直往后打，直到 $j$ 才往回走，把 $i$ 剩下的 boss 打死。

那么我们为什么不在被迫移动到 $i+1$ 的时候就直接回去把 boss 打死？这肯定更优。

想明白了这个，剩下就很简单了。

然后考虑用什么方式把 $i$ 清完。

这里我读错题了，没看到 $r_1 \le r_2 \le r_3$。

既然这样，那么每个房间只有这几种方法：

1. 手枪打小怪，AWP 打 boss。
2. 用激光枪（或手枪）对所有人各打一点伤害，被迫移动后，再移动回来，然后手枪解决 boss。

转移很简单。

注意最后终点可能是 $n-1$，也可能是 $n$。

Keshi in Search of AmShZ *2300

竟然是原理题。

读完题后又瞬间想到一个假贪心：把最短路以外的边封掉，然后强制走最短路。

显然不正确。我们可以少封一些边，然后走最长路，这样代价可以更小。

考虑这张图确定了下来，那么对方一定会走最长路。

设 $f_u$ 表示 $u$ 到 $n$ 的最大代价。

考虑一条边 $(u,v)$，如果我们经过了这条边，那么说明经过 $u$ 必须是一条最长路。

那么我们必须把比 $u$ 还长的删掉。即转移为

$$f_u=\min_{v \in to_u} (f_v+1+\sum_{v'\in to_u} [f_{v'}>f_v])$$

直接转移复杂度是炸的。

那么能不能在反图上跑时转移呢？

但是如果倒着转移的话，无法确定 $\sum_{v'\in to_u} [f_{v'}>f_v])$ 的值。

所以我们钦定转移顺序，让 $f_v$ 从小到大转移，这样 $\sum_{v'\in to_u} [f_{v'}>f_v])$ 就满足了单调性。

用优先队列维护最小即可。

复杂度 $O((n+m)\log m)$