从各大 OJ(主要是 CF)上选取的 DP 题目,重点在于 DP 的技巧和状态,较少涉及 DP 优化。
题目分为三类:
一种是基础题,考察基本的 DP 算法,如:
P8816 考察基本的线性 DP。
P2466 考察简单的区间 DP。
CF55D 考察简单的数位 DP。
一种是展示经典 DP 技巧的题目,如:
CF1327F 告诉你在转移远小于状态数时的优化。
ABC277G 告诉你如何使用组合意义描述 DP。
P8502 展示了合理状态设计的重要性。
还有一些排列问题,展示了几种基本的生成排列的方式。
以及一些较为巧妙或困难的问题,但是总体难度不会太高,因为在校内是面向 NOIP 选手的作业题。
CF2034F2 利用组合意义优化经典
CF2066D2 巧妙的状态设计。
本题单同时用作校内训练的作业题单,可能不定期更新。