0x5E 总结与练习

本章内容主要涉及两个方面：一是动态规划的模型构建方法，包括线性模型（一般的线性DP、背包、区间DP）和树形模型（一般的树形DP、背包类树形DP）；二是动态规划的优化，包括状态优化（状态压缩、倍增）和转移优化（数据结构优化、单调队列优化、斜率优化、四边形不等式）。另外，本章也涉及了环形DP和有后效性DP的处理手段、计数类DP与数位统计问题的求解等。动态规划算法的综合性较高，对问题模型抽象、关键信息提炼、算法框架设计和程序细节实现的训练都有很大帮助。

本章知识点

线性DP

理解动态规划的“阶段”“状态”“决策”三要素

应用动态规划的三个条件：“子问题重叠性”“最优子结构”“无后效性”

能抽象出题目关键点作为状态，并选择覆盖整个状态空间的最小维度集合简单状态转移方程的设计与实现

通过记录转移来源、递归输出的方法，求出动态规划算法的具体方案

DP的初步优化：离散化、贪心、变量维护决策集合、前缀和预处理等方法

背包

了解0/1背包、完全背包、多重背包、分组背包模型

在传统线性DP基础上省略“阶段”维度，控制循环顺序进行背包DP的手段多重背包的二进制拆分优化

区间DP

区间DP的状态设计

区间DP的一般转移方式：枚举划分点

DP的两种等价实现方式：递推（循环）与递归（记忆化搜索）

线性DP中“区间”与树形结构中“子树”的联系

树形DP

树形DP的状态设计

树形DP的实现方式：深度优先遍历

背包类树形DP的实现方式：分组背包转移

不定根的树形DP：二次扫描与换根法

环形与后效性处理

环形DP两种手段，两次DP（一次断开、一次强制连接）、环拆成链复制一倍高斯消元求解有后效性的状态转移方程

状态压缩DP

状态压缩DP的状态表示：集合型状态压缩为整数状态的方法，相关的位运算状态压缩DP的状态转移：一般转移、DFS转移、合法性判定

倍增优化DP

倍增优化DP的状态表示与转移方程设计

倍增优化DP的实现：先用动态规划预处理，再用二进制拆分思想进行拼接

数据结构优化DP

用线段树、树状数组、二叉堆等，维护决策候选集合，优化DP的转移

单调队列优化DP

能够确定决策的取值范围并挖掘其单调性

状态转移方程的变形，分开“只含状态变量”和“只含决策变量”的部分单调队列优化DP的程序实现框架

单调队列的三种通用操作：检查队头合法性、取最优、队尾插入并维护单调性多重背包的单调队列优化算法

斜率优化

斜率优化与线性规划的联系，建立坐标系，使用斜率和截距分析凸壳形状单调队列维护凸壳的三种通用操作

插入的坐标或待查询的斜率不具有单调性时的解决方法：二分、平衡树费用提前计算思想

四边形不等式

四边形不等式的定义和相关定理

一维线性DP、二维区间DP的四边形不等式优化

决策单调性证明、维护与实现

计数类DP

计数类 DP “不重不漏”的基本原则，加法原理与乘法原理

子问题互斥性，寻找“基准点”的思想，围绕基准点构造一个不可划分的整体

数位统计DP

数位统计问题的常见模型与求解方法：动态规划预处理、试填法

$\spadesuit$ 练习

1. 完成本章中所有例题的代码实现（标有*的题目选做）
   2.乌龟棋

题目地址：NOIP2010/TYVJ1402，提示：线性DP

3.花店橱窗

题目地址：IOI1999/TYVJ1124，提示：线性DP/输出方案

1. BUY LOW BUY LOWER

题目地址：POJ1952，提示：线性DP/统计LIS方案数

1. Trip

题目地址：POJ1934，提示：线性DP/统计LCS方案并输出

1. SUBSTRUCT

题目地址：POJ1722，提示：线性DP

7.*陨石的秘密

题目地址：NOI2001/POJ1187，提示：线性DP

8.划分大理石

题目地址：TYVJ1194，提示：背包/多重背包

1. Folding

题目地址：POJ2176，提示：区间DP

10.能量项链

题目地址：NOIP2006/TYVJ1056，提示：区间DP/环拆链并复制一倍

1. 棋盘分割

题目地址：NOI1999/POJ1191，提示：区间DP/二维平面上的区间DP

1. *Blocks

题目地址：POJ1390，提示：区间DP

13.Strategic game

题目地址：POJ1463，提示：树形DP

1. Bribing FIPA

题目地址：POJ3345，提示：树形DP/背包类树形DP

1. Computer

题目地址：HDOJ2196，提示：树形DP/二次扫描与换根法

1. XOR和路径

题目地址：BZOJ2337，提示：有后效性DP/高斯消元/数学期望

1. Corn Fields

题目地址：POJ3254，提示：状态压缩DP

1. *Bugs Integrated Inc

题目地址：POJ1038，提示：状态压缩DP

1. Fence Obstacle Course

题目地址：POJ2374，提示：线段树优化DP

1. Estimation

题目地址：HDOJ4261，提示：堆优化DP/中位数

21.干草堆

题目地址：BZOJ1233，提示：单调队列优化DP/贪心

1. 股票交易

题目地址：BZOJ1855，提示：单调队列优化DP

1. Largest Submatrix

题目地址：HDOJ2870，提示：单调队列优化DP

1. K-Anonymous Sequence

题目地址：POJ3709，提示：斜率优化

1. *特别行动队

题目地址：API02010/BZOJ1911，提示：斜率优化

1. Post Office

题目地址：IOI2000/POJ1160，提示：四边形不等式

27.*扑克牌

题目地址：Hihocoder1159/BZOJ1079，提示：计数类DP

1. The Counting Problem

题目地址：POJ2282，提示：数位统计DP

1. Round Numbers

题目地址：POJ3252，提示：数位统计DP