苟且的狮子

题解

2020多校(6) CF(27) 作业(3) 区域赛真题题解(提升思维！！！)(8) 寒假模拟赛(1) 未归档(1) 苏州大学排位赛(7) 随笔(1)

/ 注册

全部文章 / 题解（共3篇）

最优贸易

循环dp、spfa、松弛操作题意：分析：其实，我标签里的所谓循环dp其实也就是类似分层图。不过是另一种角度看待问题而已。我认为对于状态相互转移的图论问题应该适用。首先，让我们回顾一下Bellman-Ford算法。Bellman-Ford在试图解决最短路问题时总结了一个状态转移公式：d[i...

分层图循环dp

2020-08-02

3 734

追债之旅

松弛操作，循环dp 题意：分析：又是这种题，很好，对于已经明白松弛操作与循环dp的我来说已经不成问题了。给出dp状态dp[i][j] 指在第j步到达节点i的最短路径d[i][j] = min(d[k][j-1] + edge(i,k) + cost[j] k为i相邻节点)这是个无限...

Dijstra 循环dp Bellman-Ford

2020-07-29

2 696

Rinne Loves Graph

dp松弛问题(循环特性) 题意：分析： dp松弛问题。这是我的总结。所谓的最短路，不过是dp只不过该dp无法借由循环和记忆化搜索实现(因为有环使其左右横跳)详细见我的另一篇题解，正好是题单中的下一题：https://blog.nowcoder.net/n/8316b13c345d49b08b2...

Dijstra dp Bellman-Ford 循环dp

2020-07-28

6 676