《算法竞赛进阶指南》0x50动态规划‮‮

题单介绍

# 《算法竞赛进阶指南》0x50动态规划 ### 0x51 线性 DP - Mr Young\`s Picture Permutations 【ICPC New York 2004 / AcWing 271 / [SP15637](https://www.luogu.com.cn/problem/SP15637)】 - LCIS 最长公共上升子序列 【[AcWing 272](https://www.acwing.com/problem/content/274/) / [CodeForces #10 D](https://www.luogu.com.cn/problem/CF10D)（需要输出方案）】 - Making the Grade 【USACO 2008 Feb. / AcWing 273 / [Luogu P2893](https://www.luogu.com.cn/problem/P2893)】 - Mobile Service 【CEOI 2005 / AcWing 274 / [SPOJ 703](https://www.luogu.com.cn/problem/SP703)】 - 传纸条 【CCF NOIP 2008 / AcWing 275 / [Luogu P1006](https://www.luogu.com.cn/problem/P1006)】 - I-country 【Saratov State Univ. / [AcWing 276](https://www.acwing.com/problem/content/278/)】 - Cookies 【SPb NRU ITMO / [AcWing 277](https://www.acwing.com/problem/content/279/)】 ### 0x52 背包 - 数字组合 【AcWing 278 / [Luogu P1164](https://www.luogu.com.cn/problem/P1164)】 - 自然数拆分 Lunatic 版 【[AcWing 279](https://www.acwing.com/problem/content/281/)】 - Jury Compromise 【ICPC SWERC 1996 / ACWing 280 / [UVA 323](https://www.luogu.com.cn/problem/UVA323)】 - Coins 【[AcWing 281](https://www.acwing.com/problem/content/283/)】 ### 0x53 区间 DP - 石子合并 【CCF NOI 1995 / AcWing 282 / [Luogu P1880](https://www.luogu.com.cn/problem/P1880)】 - Polygon 【IOI 1998 / AcWing 283 / [Luogu P4342](https://www.luogu.com.cn/problem/P4342)】 - 金字塔 【Nescafe 12 / [AcWing 284](https://www.acwing.com/problem/content/286/)】 ### 0x54 树形 DP - 没有上司的舞会 【福建省历届夏令营 / AcWing 285 / [Luogu P1352](https://www.luogu.com.cn/problem/P1352)】 - 选课 【CTSC 1997 / AcWing 286 / [Luogu P2014](https://www.luogu.com.cn/problem/P2014)】 - Accumulation Degree 【AIPC South Central China 2008 / [AcWing 287](https://www.acwing.com/problem/content/289/)】 ### 0x55 环形与后效性处理 - Naptime 【USACO 2005 Jan. / AcWing 288 / [Luogu P6064](https://www.luogu.com.cn/problem/P6064)】 - 环路运输 【[AcWing 289](https://www.acwing.com/problem/content/291/)】 - Broken Robot 【AcWing 290 / [CodeForces #24 D](https://www.luogu.com.cn/problem/CF24D)】 ### 0x56 状态压缩 DP - Mondriaan\`s Dream 【ACM Ulm Local 2000 / [AcWing 291](https://www.acwing.com/problem/content/293/)】 - 炮兵阵地 【CCF NOI 2001 / AcWing 292 / [Luogu P2704](https://www.luogu.com.cn/problem/P2704)】 - 宝藏 【CCF NOIP 2017 / AcWing 529 / [Luogu P3959](https://www.luogu.com.cn/problem/P3959)】 ### 0x57 倍增优化 DP - 开车旅行 【CCF NOIP 2012 / AcWing 293 / [Luogu P1081](https://www.luogu.com.cn/problem/P1081)】 - Count The Repetitions 【LeetCode / [AcWing 294](https://www.acwing.com/problem/content/296/)】 ### 0x58 数据结构优化 DP - Cleanint Shifts 【USACO 2005 Dec. / AcWing 295/296 / [Luogu P4644](https://www.luogu.com.cn/problem/P4644)】 - The Battle of Chibi 【CCPC 2015 / AcWing 297 / [UVA 12983](https://www.luogu.com.cn/problem/UVA12983)】 ### 0x59 单调队列优化 DP - Fence 【Romania OI 2002 / [AcWing 298](https://www.acwing.com/problem/content/300/)】 - Cut the Sequence 【PKU / [AcWing 299](https://www.acwing.com/problem/content/301/)】 ### 0x5A 斜率优化 - 任务安排 1 【AcWing 300 / [Luogu P2365](https://www.luogu.com.cn/problem/P2365)】 - 任务安排 2 【IOI 2002 / [AcWing 301](https://www.acwing.com/problem/content/303/)】 - 任务安排 3 【SDOI 2012 / AcWing 302 / [Luogu P5785](https://www.luogu.com.cn/problem/P5785)】 - 任务安排 4 【无】 - Cats Transport 【AcWing 303 / [CodeForces #311 B](https://www.luogu.com.cn/problem/CF311B)】 ### 0x5B 四边形不等式 - 诗人小 G 【CCF NOI 2009 / AcWing 304 / [Luogu P1912](https://www.luogu.com.cn/problem/P1912)】 - 再探石子合并 【楼天城 / AcWing 2889 / [Luogu P5569](https://www.luogu.com.cn/problem/P5569)】 ### 0x5C 计数类 DP - Gerald and Giant Chess 【AcWing 306 / [CodeForces #559 C](https://www.luogu.com.cn/problem/CF559C)】 - Connected Graph 【楼天城 / [AcWing 307](https://www.acwing.com/problem/content/309/) / [Luogu P4841](https://www.luogu.com.cn/problem/P4841)（加强版）】 - How many of them? 【Gennady Korotkevich / AcWing 308 / [Luogu P6596](https://www.luogu.com.cn/problem/P6596)】 - A Decorative Fence 【CEOI 2002 / AcWing 309 / [Luogu P7690](https://www.luogu.com.cn/problem/P7690)】 ### 0x5D 数位统计 DP - 启示录 【PKU / Nescafe 12 / [AcWing 310](https://www.acwing.com/problem/content/312/)】 - 月之谜 【AHOI 2009 / Nescafe 2 / AcWing 311 / [Luogu P4127](https://www.luogu.com.cn/problem/P4127)】 ### 0x5E 总结与练习 - 乌龟棋 【CCF NOIP 2010 / AcWing 312 / [Luogu P1541](https://www.luogu.com.cn/problem/P1541)】 - 花店橱窗 【IOI 1999 / AcWing 313 / [Luogu P1854](https://www.luogu.com.cn/problem/P1854)】 - Buy Low Buy Lower 【USACO 2002 Feb. / AcWing 314 / [Luogu P2687](https://www.luogu.com.cn/problem/P2687)】 - Trip 【CEOI 2003 / AcWing 315 / [SP33](https://www.luogu.com.cn/problem/SP33)】 - Substract 【CEOI 1998 / [AcWing 316](https://www.acwing.com/problem/content/318/)】 - 陨石的秘密 【CCF NOI 2001 / AcWing 317 / [Luogu P5694](https://www.luogu.com.cn/problem/P5694)】 - 划分大理石 【[AcWing 318](https://www.acwing.com/problem/content/320/)】 - Folding 【ICPC NEERC 2002 / AcWing 319 / [Luogu P2400](https://www.luogu.com.cn/problem/P2400)】 - 能量项链 【CCF NOIP 2006 / AcWing 320 / [Luogu P1063](https://www.luogu.com.cn/problem/P1063)】 - 棋盘分割 【CCF NOI 1999 / AcWing 321 / [Luogu P5752](https://www.luogu.com.cn/problem/P5752)】 - Blocks 【刘汝佳 / AcWing 322 / [UVA 10559](https://www.luogu.com.cn/problem/UVA10559)】 - Strategic game 【ICPC SEERC 2000 / AcWing 323 / [UVA 1292](https://www.luogu.com.cn/problem/UVA1292)】 - Bribing FIPA 【ICPC Tehran 2006 / AcWing 324 / [UVA 1222](https://www.luogu.com.cn/problem/UVA1222)】 - Computer 【[AcWing 325](https://www.acwing.com/problem/content/327/)】 - XOR 和路径 【HNOI 2011 / AcWing 326 / [Luogu P3211](https://www.luogu.com.cn/problem/P3211)】 - Island and Bridges 【ICPC Shanghai 2004 / [AcWing 1194](https://www.acwing.com/problem/content/1196/)】 - Corn Fields 【USACO 2006 Nov. / AcWing 327 / [Luogu P1879](https://www.luogu.com.cn/problem/P1879)】 - Bugs Integrated Inc 【CEOI 2002 / AcWing 328 / [Luogu P7689](https://www.luogu.com.cn/problem/P7689)】 - Fence Obstacle Cource 【USACO 2004 Dec. / [AcWing 329](https://www.acwing.com/problem/content/331/)】 - Estimation 【The Univ. of Chicago / AcWing 330 / [SPOJ 16809](https://www.luogu.com.cn/problem/SP16809)】 - 干草堆 【USACO 2009 Open / AcWing 331 / [Luogu P4954](https://www.luogu.com.cn/problem/P4954)】 - 股票交易 【SCOI 2010 / AcWing 332 / [Luogu P2569](https://www.luogu.com.cn/problem/P2569)】 - Largest Submatrix 【Multi-Univ. Training / [AcWing 333](https://www.acwing.com/problem/content/335/)】 - K-Anonymous Sequence 【PKU / [AcWing 334](https://www.acwing.com/problem/content/336/)】 - 特别行动队 【APIO 2010 / AcWing 335 / [Luogu P3628](https://www.luogu.com.cn/problem/P3628)】 - Post Office 【IOI 2000 / AcWing 336 / [Luogu P4767](https://www.luogu.com.cn/problem/P4767)】 - 扑克牌 【微软编程之美 2015 初赛 2 / [AcWing 337](https://www.acwing.com/problem/content/339/)】 - The Counting Problem 【ICPC Shanghai 2004 / AcWing 338 / [UVA 1640](https://www.luogu.com.cn/problem/UVA1640)】 - Round Numbers 【USACO 2006 Nov. / AcWing 339 / [Luogu P6218](https://www.luogu.com.cn/problem/P6218)】

题目列表

  • GNYR04H - Mr Youngs Picture Permutations
  • LCIS
  • [USACO08FEB] Making the Grade G
  • SERVICE - Mobile Service
  • [NOIP 2008 提高组] 传纸条
  • 小A点菜
  • Jury Compromise
  • [NOI1995] 石子合并
  • [IOI 1998] Polygon
  • 没有上司的舞会
  • [CTSC1997] 选课
  • [USACO05JAN] Naptime G
  • Broken robot
  • [NOI2001] 炮兵阵地
  • [NOIP 2017 提高组] 宝藏
  • [NOIP 2012 提高组] 开车旅行
  • [USACO05DEC] Cleaning Shifts S
  • The Battle of Chibi
  • 任务安排
  • [SDOI2012] 任务安排
  • Cats Transport
  • [NOI2009] 诗人小G
  • [SDOI2008] 石子合并
  • Gerald and Giant Chess
  • How Many of Them
  • [CEOI 2002] A decorative fence
  • [AHOI2009] 同类分布
  • [NOIP 2010 提高组] 乌龟棋
  • 花店橱窗布置
  • [USACO4.3] 逢低吸纳Buy Low, Buy Lower
  • TRIP - Trip
  • [NOI2001] 陨石的秘密
  • 秘密文件
  • [NOIP 2006 提高组] 能量项链
  • [NOI1999] 棋盘分割
  • 方块消除 Blocks
  • Strategic game
  • Bribing FIPA
  • [HNOI2011] XOR和路径
  • [USACO06NOV] Corn Fields G
  • [CEOI 2002] Bugs Integrated,Inc.
  • EST - Estimation
  • [USACO09OPEN] Tower of Hay G
  • [SCOI2010] 股票交易
  • [APIO2010] 特别行动队
  • [IOI 2000] 邮局 加强版
  • 统计问题 The Counting Problem
  • [USACO06NOV] Round Numbers S