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