本题是否有最短路做法？

P2627 [USACO11OPEN] Mowing the Lawn G

xs_siqi @ 2022-08-26 22:00:55

RT。蒟蒻刚学线段树优化建图，看了一眼题面打了个线段树优化建图加了个dij。通过记录。

但题解区全是单调队列加dp。感觉最短路实际也是可行的。求大佬看下该解法是否可行，如果可行想写个题解提交给管理员。

具体思路如下：

  • 将 i 与 [i+1,i+k+1] 区间连边，边权为 a[i]，当然，[i+k+1]\leq n+1。

  • 添加超级节点 n+1 与 i+k+1>n+1 的节点连边。 每次暴力连 a[i]。

因为这建边是 O(nk) 的，考虑使用线段树优化建边。

我知道有个人在P2034发了个这样的题解，然而他的线段树建边解法较复杂，最重要的是他带两个 log，而我的能优化到一个 log。

by xs_siqi @ 2022-08-26 22:01:47

忘记补充了，最后答案为节点权值和减去节点 1 到 n+1 的最短路。

by Usada_Pekora @ 2022-08-26 22:05:04

@xs_siqi 注意这篇题解建边是单 \log 的。

by Usada_Pekora @ 2022-08-26 22:08:46

且本质和本题题解 1 的做法没有区别。

by xs_siqi @ 2022-08-26 22:10:23

@Zyingyzzz 题解区写的不都是dp吗

by Usada_Pekora @ 2022-08-26 22:10:31

你确定你这个代码是单 \log 的？

by xs_siqi @ 2022-08-26 22:10:39

重新看了下，他的写法的确是单log

by Usada_Pekora @ 2022-08-26 22:11:09

@xs_siqi 题解 1 做法 3， \sum ^n_{i=1}E_i - f_{n+1}。

by xs_siqi @ 2022-08-26 22:12:29

@Zyingyzzz 好吧的确是这样。我看到他用dp就直接放过去了

by xs_siqi @ 2022-08-26 22:12:38

此帖结

|