OI 知识总览 算法篇 之 动态规划

OI 复习 dp

一) 区间dp

题目

1. [NOI1995]石子合并
2. 能量项链

二) 树型dp

题目

1. [ZJOI2008]骑士

三) 数位dp

虽说是dp, 其实更多是按照记忆化搜索的形式来写, 更容易理解, 也更好调试.

题目

1. [SCOI2009]windy数

四) 状压dp

题目

1. [NOI2001]炮兵阵地
2. [APIO2007]动物园

五) 数据结构优化dp

算法

1. 单调队列优化dp
2. 树状数组优化dp
3. .....

六) 斜率优化dp