retep

分类

笔记(6) 题解(2)

/ 注册

全部文章（共3篇）

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

若有方程 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

题解 | #牛牛的计算机内存#

题意可以对 nnn 条 010101 字符串进行任意排序，排好序后的代价为从前往后每次加入新 010101 串后多出 111 位置数的平方的累加。解法本体是经典的状态压缩，状态表示的是m块内存哪些已经访问过了。用记忆化搜索实现非常方便。函数传递的参数为已经访问过几块内存了、n个位置中哪些位置...

C++ 动态规划

2022-05-12

1 593