Codeforces DP题单

【CF 1200-1600 - 动态规划】(简单DP)

• CF455A Boredom (线性DP，取或不取)
• CF189A Cut Ribbon (完全背包思想/线性DP)
• CF414B Mashmokh and ACM (线性DP，约数关系)
• CF431C k-Tree (树形结构思想的DP，计数)
• CF711C Coloring Trees (线性DP，多维状态)
• CF1097B Petr and a Combination Lock (简单背包/DFS)
• CF118D String Task (Incorrect name, actually about sequences) (线性DP，计数，相邻限制)
• CF580A Kefa and First Steps (LIS变种，最长连续非降)
• CF474D Flowers (线性DP + 前缀和)
• CF1352E Special Elements (前缀和 + 暴力/DP判断)
• CF607A Chain Reaction (线性DP，排序后处理依赖)
• CF628C Bear and String Distance (构造，但DP思想可用于检查)
• CF1133C Balanced Team (排序 + 双指针，类似LIS的O(N log N)思想)
• CF1343D Constant Palindrome Sum (贡献法/差分数组，有点DP思想)
• CF977F Consecutive Subsequence (LIS变形，map优化)
• CF1324E Sleeping Schedule (线性DP)
• CF1220A Cards (计数，简单模拟)
• CF467C George and Job (线性DP，选k段不重叠子段和最大)
• CF1105C Ayoub and Lost Array (线性DP，模意义下计数)
• CF2B The least round way (二维DP，分别记录2和5的因子数)
• CF1350B Orac and Models (线性DP，约数倍数关系)
• CF1399D Binary String To Subsequences (贪心/DP思想构造)
• CF1426F Number of Subsequences (线性DP，计数 abc)
• CF1015C Songs Compression (贪心/01背包思想)
• CF327A Flipping Game (最大子段和变种)
• CF165C Another Problem on Strings (前缀和 + map/hash，计数)
• CF988D Points and Powers of Two (暴力/构造，但可以DP检查)
• CF1200E Compress Words (KMP思想，但DP可以求最长公共前后缀)
• CF1300B Assigning to Classes (排序+二分/中位数思想)
• CF546D Soldier and Number Game (预处理质因子 + DP)

【CF 1600-2100 - 动态规划】(中等DP与常见模型)

• CF149D Coloring Brackets (区间DP，括号序列)
• CF1195C Basketball Exercise (简单线性DP，两行选择)
• CF543A Writing Code (多维背包DP)
• CF363D Renting Bikes (二分答案 + 贪心/DP判断)
• CF835D Palindromic characteristics (区间DP，统计回文串)
• CF1061C Multiplicity (线性DP，约数关系)
• CF1327D Infinite Path (图论 + DP，找环)
• CF698A Vacations (线性DP，状态记录前一天活动)
• CF1253D Harmonious Graph (并查集 + 区间合并思想，类似DP)
• CF118E Bertown roads (Tarjan找桥 + DFS树定向，图论DP)
• CF909C Python Indentation (计数DP，模拟缩进规则)
• CF489D Unbearable Controversy of Being (图论计数，三元环思想，可DP)
• CF706D Vasiliy's Multiset (01Trie维护异或最大值，类似DP选择)
• CF1301D Time to Run (构造路径，但DP思想可用于规划)
• CF1238D AB-string (计数，考虑贡献/DP)
• CF1036C Classy Numbers (数位DP)
• CF1114D Flood Fill (区间DP)
• CF1295D Same GCDs (数论 + 容斥/DP)
• CF862B Mahmoud and Ehab and the bipartiteness (二分图染色 + 简单计数)
• CF1285D Dr. Evil Underscores (01Trie + 分治/DP)
• CF1107D Compression (二维前缀和/哈希，判断子块是否相同)
• CF229D Towers (线性DP，决策单调性可能)
• CF1178D Prime Graph (构造素数边数的图)
• CF1076E Vasya and a Tree (DFS序 + 树状数组/线段树维护DP值)
• CF358D Dima and Hares (线性DP，相邻选择影响)
• CF461B Appleman and Tree (树形DP，计数黑色节点连通块)
• CF1359E Modular Stability (组合计数DP)
• CF1208D Restore Permutation (线段树/树状数组模拟，逆向思维)
• CF1027D Mouse Hunt (基环树找最小环权值和)
• CF505C Mr. Kitayuta, his dish and stones (记忆化搜索/线性DP，状态记录步长)

【CF 2100-2500+ - 动态规划】(高级DP与优化)

• CF1083E The Fair Share (斜率优化DP)
• CF311B Cats Transport (斜率优化DP/单调队列优化DP)
• CF808G Anthem of Berland (KMP自动机/AC自动机上DP)
• CF983B XOR-sum (区间DP，ST表优化查询)
• CF678F Lena and Queries (李超线段树/分治凸包维护DP)
• CF1117D Magic Gems (矩阵快速幂优化DP)
• CF95E Lucky Country (并查集 + 背包DP计数)
• CF833B The Bakery (DP + 线段树优化转移)
• CF1097D Makoto and a Blackboard (期望DP，质因数分解)
• CF19B Checkout Assistant (背包DP，费用提前计算思想)
• CF568C New Language (2-SAT / DFS构造 + 字典序最小) - 虽然不是纯DP，但构造过程类似
• CF739C Alyona and towers (线段树维护复杂DP信息，区间合并)
• CF1292C Xenon's Attack on the Gangs (树形DP，计算路径贡献)
• CF1007B Pave the Parallelogram (容斥原理 + 组合计数DP)
• CF868F Yet Another Minimization Problem (决策单调性分治/莫队思想优化DP)
• CF1304F2 Animal Observation (hard version) (DP + 单调队列/滑动窗口优化)
• CF1101D GCD Counting (树形DP，维护质因子信息)
• CF960F Pathwalks (DAG上DP，用map/平衡树优化按权值转移)
• CF1051F The Shortest Statement (建出部分点构成的虚树/关键点最短路 + 树上路径)
• CF1209G2 Into Blocks (hard version) (贪心 + 单调栈/线段树维护区间信息，类似DP决策)
• CF559C Gerald and Giant Chess (容斥原理 + 路径计数DP)
• CF1225F Tree Factory (树的性质 + 构造/DP)
• CF115E Linear Kingdom Races (线段树优化DP，区间最大子段和思想)
• CF1073E Segment Sum (数位DP)
• CF467E Berland Local Positioning System (DP + 单调栈/笛卡尔树思想)
• CF888G Xor-MST (Boruvka算法 + 01Trie) - 虽是MST，但Trie上操作有DP思想
• CF626F Group Projects (计数DP，状态设计复杂)
• CF1082E Increasing Frequency (线性DP，转化问题为最大子段和)
• CF1029F Multicolored Markers (枚举 + 优化，但DP可以求最小周长)
• CF938E Erasing Substrings (期望DP/贡献法)