DP 技巧与进阶

从各大 OJ(主要是 CF)上选取的 DP 题目,重点在于 DP 的技巧和状态,较少涉及 DP 优化。

题目分为三类:

一种是基础题,考察基本的 DP 算法,如:

一种是展示经典 DP 技巧的题目,如:

以及一些较为巧妙或困难的问题,但是总体难度不会太高,因为在校内是面向 NOIP 选手的作业题。

本题单同时用作校内训练的作业题单,可能不定期更新。


  1. P8816 - [CSP-J 2022] 上升点列
  2. AT_arc132_c - [ARC132C] Almost Sorted
  3. CF1327F - AND Segments
  4. CF1943D1 - Counting Is Fun (Easy Version)
  5. CF1886E - I Wanna be the Team Leader
  6. AT_abc277_g - [ABC277G] Random Walk to Millionaire
  7. CF1542E1 - Abnormal Permutation Pairs (easy version)
  8. P9847 - [ICPC 2021 Nanjing R] Crystalfly
  9. P2466 - [SDOI2008] Sue 的小球
  10. P11233 - [CSP-S 2024] 染色
  11. CF1806D - DSU Master
  12. CF559C - Gerald and Giant Chess
  13. P8502 - 「CGOI-2」No cost too great
  14. AT_abc282_g - [ABC282G] Similar Permutation
  15. CF176D - Hyper String
  16. CF840C - On the Bench
  17. CF1523D - Love-Hate
  18. CF1437F - Emotional Fishermen
  19. CF1616H - Keep XOR Low
  20. CF1856E2 - PermuTree (hard version)
  21. CF55D - Beautiful numbers
  22. CF730F - Ber Patio
  23. CF1845E - Boxes and Balls
  24. CF1111D - Destroy the Colony
  25. CF1566F - Points Movement
  26. CF1580D - Subsequence
  27. CF1781F - Bracket Insertion
  28. P2150 - [NOI2015] 寿司晚宴
  29. P3413 - SAC#1 - 萌数
  30. CF1765C - Card Guessing
  31. CF1796E - Colored Subgraphs
  32. AT_abc309_g - [ABC309G] Ban Permutation
  33. AT_abc267_g - [ABC267G] Increasing K Times
  34. AT_abc213_g - [ABC213G] Connectivity 2
  35. P8867 - [NOIP2022] 建造军营
  36. CF1730F - Almost Sorted
  37. P11363 - [NOIP2024] 树的遍历
  38. CF2066D2 - Club of Young Aircraft Builders (hard version)
  39. CF2034F2 - Khayyam's Royal Decree (Hard Version)
  40. CF1174E - Ehab and the Expected GCD Problem
  41. CF1889C2 - Doremy's Drying Plan (Hard Version)
  42. CF722E - Research Rover
  43. CF1184D2 - Parallel Universes (Hard)