转存的 面向tg选手的DP练习题

题单介绍

# DP综述 - 最优子结构:把原问题化到**规模更小**的问题后,原问题的最优解一定能从**规模更小**问题的**最优解**推出。 - 无后效性:如果在某个阶段上过程的状态已知,则从此阶段**以后过程的发展变化仅与此阶段的状态有关**,而与过程在此阶段以前的阶段所经历过的状态无关。 - 状态:类似搜索中所说的状态,就是怎么描述求解过程中的一个阶段。希望状态完整而不冗余地定义清楚子问题。 - 为什么动态规划和搜索相比更优秀?我们找出转移模式相同的、本质类似的那些状态,将其合并在一个新状态中,从而减少总的状态数量和转移路径数量。 --- # 解题套路 - 寻找子问题 - 设计状态描述 - 写出转移规则 - 确定边界 --- # 线性DP 往往用$F_{i,s}$表示区间$[1,i]$在状态限制$s$下的最优解。 ### 例题 [P4310 绝世好题](https://www.luogu.com.cn/problem/P4310) [P1944 最长括号匹配](https://www.luogu.com.cn/problem/P1944) [P1772 [ZJOI2006]物流运输](https://www.luogu.com.cn/problem/P1772) --- # 背包DP - 01背包 - 完全背包 - 多重背包 - 二进制拆分 - 斜率优化 - 分组背包 - 树形背包 ### 例题 [P4158 [SCOI2009]粉刷匠](https://www.luogu.com.cn/problem/P4158) [P1284 三角形牧场](https://www.luogu.com.cn/problem/P1284) [P1156 垃圾陷阱](https://www.luogu.com.cn/problem/P1156) [P1941 飞扬的小鸟](https://www.luogu.com.cn/problem/P1941) [P1282 多米诺骨牌](https://www.luogu.com.cn/problem/P1282) [P5322 [BJOI2019]排兵布阵](https://www.luogu.com.cn/problem/P5322) [P2224 [HNOI2001]产品加工](https://www.luogu.com.cn/problem/P2224) [P3188 [HNOI2007]梦幻岛宝珠](https://www.luogu.com.cn/problem/P3188) [P4141 消失之物](https://www.luogu.com.cn/problem/P4141) [P4095 [HEOI2013]Eden的新背包问题](https://www.luogu.com.cn/problem/P4095) [P2851 [USACO06DEC]The Fewest Coins G](https://www.luogu.com.cn/problem/P2851) --- # 区间DP 依照子区间来定义子问题。 大区间的求解依赖于其内部小区间的求解。 往往用$F_{l,r,s}$表示区间$[l,r]$在状态限制$s$下的最优解。 按照区间长度从小到大依次求解。 单点构成的区间或空区间无需递归。 **TIPS :尝试下面三种转移思路** - $F_{l,r,s} = max{F_{l+1,r,s'},F_{l,r-1,s'}}$ - $F_{l,r,s} = max_{l\leq k<r}{f(F_{l,k,s'},F_{k+1,r,s'})}$ - $F_{l,r,s} = max_{l\leq k\leq r}{f(F_{l,k,s'},F_{k,r,s'})}$ ### 例题 [P1040 加分二叉树](https://www.luogu.com.cn/problem/P1040) [CF607B Zuma](https://www.luogu.com.cn/problem/CF607B) [P2890 [USACO07OPEN]Cheapest Palindrome G](https://www.luogu.com.cn/problem/P2890) [P4170 [CQOI2007]涂色](https://www.luogu.com.cn/problem/P4170) [UVA1437 String painter](https://www.luogu.com.cn/problem/UVA1437) [CF149D Coloring Brackets](https://www.luogu.com.cn/problem/CF149D) [P5851 [USACO19DEC]Greedy Pie Eaters P](https://www.luogu.com.cn/problem/P5851) [UVA1629 切蛋糕 Cake slicing](https://www.luogu.com.cn/problem/UVA1629) [P3205 [HNOI2010]合唱队](https://www.luogu.com.cn/problem/P3205) # 树形DP 问题定义在树形结构上,依照子树设定子问题。 常常用$F_{u,s}$表示子树$u$在状态限制$s$下的最优解。 先递归求解子树的答案,再计算当前结点答案。 ## 普通树形DP ### 例题 [P1122 最大子树和](https://www.luogu.com.cn/problem/P1122) [P1352 没有上司的舞会](https://www.luogu.com.cn/problem/P1352) [P4084 [USACO17DEC]Barn Painting G](https://www.luogu.com.cn/problem/P4084) [P2016 战略游戏](https://www.luogu.com.cn/problem/P2016) [P2458 [SDOI2006]保安站岗](https://www.luogu.com.cn/problem/P2458) [P3621 [APIO2007]风铃](https://www.luogu.com.cn/problem/P3621) [P4099 [HEOI2013]SAO](https://www.luogu.com.cn/problem/P4099) [P3174 [HAOI2009]毛毛虫](https://www.luogu.com.cn/problem/P3174) [P3237 [HNOI2014]米特运输](https://www.luogu.com.cn/problem/P3237) ## 树形依赖背包 要选取一个结点上的物品,需要选取其父结点的物品。 - 朴素写法:枚举子树分配体积(01背包用点对数量分析) - 2009年国家集训队论文 徐持衡《浅谈几类背包题》 - 借助DFS序拍平成线性结构 ###### DFS序为$i$的点子树大小为$S_i$,体积为$W_i$,价值为$V_i$,$F_{i,j}=\max\{F_{i+S_i,j},F_{i+1,j-W_i}+V_i\}$ (i从大到小倒序枚举) --- ### 例题 [P1273 有线电视网](https://www.luogu.com.cn/problem/P1273) [P2014 [CTSC1997]选课](https://www.luogu.com.cn/problem/P2014) [P2015 二叉苹果树](https://www.luogu.com.cn/problem/P2015) [P3177 [HAOI2015]树上染色](https://www.luogu.com.cn/problem/P3177) [P3354 [IOI2005]Riv 河流](https://www.luogu.com.cn/problem/P3354) [P1270 “访问”美术馆](https://www.luogu.com.cn/problem/P1270) [P4322 [JSOI2016]最佳团体](https://www.luogu.com.cn/problem/P4322) [P1272 重建道路](https://www.luogu.com.cn/problem/P1272) [P4037 [JSOI2008]魔兽地图](https://www.luogu.com.cn/problem/P4037) --- ## 换根 - 先以1为根结点,求出$F_u$表示$u$子树的最优解 - 考虑将根结点换到1的邻点2上,只有1和2两个结点的相对关系发生变化,快速地计算出新的$F_1$和$F_2$ - 继续换根直到尝试过以每个点为根结点 - 回溯操作就是递归操作的逆 ### 例题 [ P3478 [POI2008]STA-Station](https://www.luogu.com.cn/problem/P3478) [ P2986 [USACO10MAR]Great Cow Gathering G](https://www.luogu.com.cn/problem/P2986) [P3047 [USACO12FEB]Nearby Cows G](https://www.luogu.com.cn/problem/P3047) [P5898 [COCI 2015]Kamp](https://www.luogu.com.cn/problem/P5898) [P3647 [APIO2014]连珠线](https://www.luogu.com.cn/problem/P3647) ## 基环树DP ### 例题 [P1453 城市环路](https://www.luogu.com.cn/problem/P1453) [P2607 [ZJOI2008]骑士](https://www.luogu.com.cn/problem/P2607) ---

题目列表

  • 绝世好题
  • 最长括号匹配
  • [ZJOI2006] 物流运输
  • 三角形牧场
  • [SCOI2009] 粉刷匠
  • 垃圾陷阱
  • [HEOI2013] Eden 的新背包问题
  • 消失之物
  • [HNOI2007] 梦幻岛宝珠
  • [NOIP2014 提高组] 飞扬的小鸟
  • [BJOI2019] 排兵布阵
  • 多米诺骨牌
  • [HNOI2001] 产品加工
  • [USACO06DEC] The Fewest Coins G
  • [NOIP2003 提高组] 加分二叉树
  • Zuma
  • [CQOI2007] 涂色
  • [USACO07OPEN] Cheapest Palindrome G
  • Coloring Brackets
  • [USACO19DEC] Greedy Pie Eaters P
  • String painter
  • 切蛋糕 Cake slicing
  • [HNOI2010] 合唱队
  • 最大子树和
  • 没有上司的舞会
  • [USACO17DEC] Barn Painting G
  • 战略游戏
  • [SDOI2006] 保安站岗
  • [APIO2007] 风铃
  • [HEOI2013] SAO
  • [HAOI2009] 毛毛虫
  • [HNOI2014] 米特运输
  • 有线电视网
  • [CTSC1997] 选课
  • 二叉苹果树
  • [HAOI2015] 树上染色
  • [IOI2005] Riv 河流
  • “访问”美术馆
  • [JSOI2016] 最佳团体
  • 重建道路
  • [JSOI2008] 魔兽地图
  • [POI2008] STA-Station
  • [USACO10MAR] Great Cow Gathering G
  • [USACO12FEB] Nearby Cows G
  • [COCI2014-2015#1] Kamp
  • [APIO2014] 连珠线
  • 城市环路
  • [ZJOI2008] 骑士