retep

笔记

题解(2)

/ 注册

全部文章 / 笔记（共2篇）

二分队列，用于优化决策单调性动态规划的方法之一

若有方程 f[i]=min{f[j]+cost(j,i)∣j<i}f[i]=min\left\{f[j]+cost(j , i) | j<i\right\}f[i]=min{f[j]+cost(j,i)∣j<i}，这种方程一般是经典的切割问题，如果 f[i]f[i]f[i] 的最...

动态规划队列

2022-05-12

0 432

插头dp学习笔记

插头DP是一类基于连通性的状态压缩动态规划，是用状压DP处理联通问题的强劲武器。本文以P5056【模板】插头dp为例进行分析。一个格子有四个插头，上下左右，就像拼图凸出来和凹进去的地方。一个格子会选出两个插头，形成一条经过此格的路径。当两个左右在一起的格子，左边的格子选了右插头，右边的格子选了左插...

动态规划状态压缩

2022-05-12

0 501