比赛地址

试题列表

赛题 #A:P4741 [Wind Festival]Finding RhFe|满分: 100分
赛题 #B:P4742 [Wind Festival]Running In The Sky|满分: 100分
赛题 #C:P4743 [Wind Festival]Energy Center|满分: 100分
赛题 #D:P4744 [Wind Festival]Iron Man|满分: 100分
难度顺序从小到大:#B #C #D #A

Finding RhFe

Running In The Sky

思路

既然可以“到达一支风筝多次”,也就是可以走回头路,那么我们可以直接 Tarjan 缩点,在新的 DAG 上以拓扑排序的方法 DP。

代码

Energy Center

Iron Man

思路

看数据范围就知道要写一个 $O(Nk)$ 的 $DP$。 $f[i][2j-2]$ 代表加入了 $a_i$,总共使用了 $j$ 个区间的最大权值和, $f[i][2j-1]$ 代表没加入 $a_i$,总共使用了 $j$ 个区间的最大权值和。对于每一个 $a_i$,转移的时候 $O(k)$ 枚举即可。

代码