何事秋。

dp基本算法

AC自动机(4) bfs/dfs(5) bitset(3) CF刷题(23) dp一般看规律(11) KMP(2) LCA(1) LCT(4) Prufer(2) SAM(3) STL(1) tarjan(1) 主席树/线段树(14) 二分/三分(2) 二分图(1) 位运算(1) 偏序问题(2) 分块(1) 分治/点分治/边分治(2) 单调栈(2) 单调队列(1) 博弈/sg(3) 博弈论基本算法(11) 后缀数组(1) 启发式合并(1) 哈希(4) 回文自动机(2) 图论一顿套模板(3) 图论基本算法(31) 基本算法(2) 多项式(1) 套题(1) 字典树(1) 字符串基本算法(27) 容斥(1) 平衡树/堆(2) 并查集(3) 序列自动机(1) 快速幂/矩阵快速幂(1) 思维只会A+B(5) 投稿(2) 拓扑序(1) 数位dp(1) 数学不好先打表(4) 数据结构基本算法(69) 数据结构瞎乱写(8) 数论分块(1) 数论只会gcd(20) 数论基本算法(64) 暴力(1) 最短路(3) 期望/概率(1) 期望dp/概率dp(1) 构造(3) 枚举(3) 树形dp(3) 树链剖分(5) 模拟只会猜题意(5) 生成树(1) 签到题(2) 线性dp(12) 线性基(2) 组合数学(1) 组合数学靠运气(2) 结论题(2) 网络流/费用流(5) 网络流基本算法(5) 群论(2) 背包dp(1) 莫比乌斯反演(1) 莫队(1) 虚树(1) 计数类dp(1) 计算几何(8) 计算几何基本算法(15) 贪心刚好过样例(3) 随机化算法(2)

/ 注册

全部文章 / dp基本算法（共12篇）

环形结构上的动态规划问题的两种基本处理方式：

一、执行两次DP，第一次在任意位置把环断开成链，按照线性问题求解。第二次通过适当的条件和赋值，保证计算的状态等价于把断开的位置强制相连。 Naptime POJ - 2228： Goneril is a very sleep-deprived cow. Her day is partitione...

2020-09-04

0 981

有后效性的状态转移方程：

一、实际上无后效性是动态规划算法的前提之一，然后有些题，我们设计出状态表示和状态转移方程之后才发现，其似乎不满足无后效性这一特点。以以下期望dp为例，在很多的题目中，动态规划的状态转移分阶段带环，我们需要把dp和高斯消元相结合，在整体层面采用动态规划框架，在局部使用高斯消元解出互相影...

2020-09-04

0 765

数据结构优化dp：

写在前面：一般的，只要决策的候选集合只扩大，不缩小，我们就可以仅用一个变量维护最值，不断与新加入候选集合的元素比较，即可直接得到最优决策，O（1）的进行转移。在更加复杂的情况下，我们就要用更加高级的数据结构，而不仅仅是一个变量维护dp的决策候选集合，以便快速执行插入元素，删除元素，查询最值等操作...

2020-09-04

0 575

计数类dp：

写在前面：这一类dp特别要求不重不漏。统计对象的可能情况一般比较多，通常需要精确的划分和整体性计算。因此，使用动态规划抽象出问题中的子结构和推导的阶段，将有助于我们准确而高效的进行求解。在求解计数类动态规划的问题时，通常要找到一个基准点，围绕这个基准点构造一个不可划分的整体，以避免子问题之间的...

2020-09-04

0 641

倍增优化dp：

写在前面：用倍增优化的动态规划算法求解问题时，一般分为两部分，第一部分是预处理，用阶段成倍增长的DP，计算出若干与2的整数次幂相关的代表状态。第二部分是拼凑，基于二进制拆分思想，用上一部分得到的代表状态组合成最终答案。一、P1081 开车旅行：题目描述小 A 和小 B 决定利用假期外出旅行...

2020-09-04

0 695

单调队列优化dp：

用数组模拟队列速度会更快一点。一、Fence POJ - 1821: A team of k (1 <= K <= 100) workers should paint a fence which contains N (1 <= N <= 16 000) planks n...

2020-09-04

0 428

斜率优化dp：

一、任务安排1：有 N 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。从时刻0开始，任务被分批加工，执行第 i 个任务所需的时间是 Ti。另外，在每批任务开始前，机器需要 S 的启动时间，故执行一批任务所需的时...

2020-09-04

0 612

概率/期望dp：

一、Acwing 217. 绿豆蛙的归宿：给出一个有向无环的连通图，起点为1，终点为N，每条边都有一个长度。数据保证从起点出发能够到达图中所有的点，图中所有的点也都能够到达终点。绿豆蛙从起点出发，走向终点。到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，...

2020-09-04

0 397

动态dp

一、模板题：P4719 【模板】动态 DP：题目描述给定一棵n个点的树，点带点权。有m次操作，每次操作给定x,y，表示修改点x的权值为y。你需要在每次操作之后求出这棵树的最大权独立集的权值大小。输入格式第一行，n,m，分别代表点数和操作数。第二行，V1,V2,…,Vn，代表n个...

2020-09-04

0 429

插头dp/轮廓线dp

先%mmh学长。这个东西还好吧。。。。也算是个状压，难的也不会，就会写个板子题。用哈希map代替了哈希表。一、P5056 【模板】插头dp：题目背景 ural 1519 陈丹琦《基于连通性状态压缩的动态规划问题》中的例题题目描述给出n*m的方格，有些格子不能铺线，其它格子必须铺，形...

2020-09-04

0 668