竞赛算法与算法训练 · 小纸条

选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。

第 1 页 · 正面（题目）

1DP状态与DAG视角

闭卷重建DP状态与DAG视角的对象、状态、事件、不变量与一个失败反例。

2线性DP与最大子段和

闭卷重建线性DP与最大子段和的对象、状态、事件、不变量与一个失败反例。

3最长递增子序列

闭卷重建最长递增子序列的对象、状态、事件、不变量与一个失败反例。

4零一背包

闭卷重建零一背包的对象、状态、事件、不变量与一个失败反例。

5完全与多重背包

闭卷重建完全与多重背包的对象、状态、事件、不变量与一个失败反例。

6路径与计数DP

闭卷重建路径与计数DP的对象、状态、事件、不变量与一个失败反例。

7方案恢复与滚动数组

闭卷重建方案恢复与滚动数组的对象、状态、事件、不变量与一个失败反例。

第 1 页 · 背面（答案）

核心机制：围绕线性DP与最大子段和先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成线性DP与最大子段和的暴力、优化、对拍与复盘；边界：状态必须无后效；零一背包倒序、完全背包正序不能混用。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕DP状态与DAG视角先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成DP状态与DAG视角的暴力、优化、对拍与复盘；边界：状态必须无后效；零一背包倒序、完全背包正序不能混用。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕零一背包先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成零一背包的暴力、优化、对拍与复盘；边界：状态必须无后效；零一背包倒序、完全背包正序不能混用。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕最长递增子序列先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成最长递增子序列的暴力、优化、对拍与复盘；边界：状态必须无后效；零一背包倒序、完全背包正序不能混用。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕路径与计数DP先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成路径与计数DP的暴力、优化、对拍与复盘；边界：状态必须无后效；零一背包倒序、完全背包正序不能混用。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕完全与多重背包先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成完全与多重背包的暴力、优化、对拍与复盘；边界：状态必须无后效；零一背包倒序、完全背包正序不能混用。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕方案恢复与滚动数组先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成方案恢复与滚动数组的暴力、优化、对拍与复盘；边界：状态必须无后效；零一背包倒序、完全背包正序不能混用。本课必须再检查边界输入、整数溢出、下标和不可行状态。。