【动态规划6】动态规划的设计与优化
题单介绍
对应进阶篇第 18 章。
动态规划作为算法竞赛中出现频率高,且难度上限很高的话题,在状态设计以及转移的优化 上有大量的技巧。如果读者尚不能熟练构造状态,请相信熟能生巧:在大量的练习下,自然而然 就能理解如何构造状态以及如何在不同的状态之间转移。除此之外,使动态规划算法变得更加高 效也是一个重要的目标。本章将介绍如何设计动态规划,并介绍了一些动态规划的优化案例。
![](https://ipic.luogu.com.cn/zpvia7.png)
题目列表
[HAOI2009] 逆序对数列
Student's Camp
Power收集
The Bakery
[SDOI2012] 任务安排
[APIO2014] 序列分割
[NOI2007] 货币兑换
[ARC081F] Flip and Rectangles
缩小社交圈
[HEOI2013] SAO
[POI2014] PTA-Little Bird
[NOI2005] 瑰丽华尔兹
[SCOI2010] 股票交易
[NOI2011] NOI 嘉年华
[JSOI2011] 柠檬
[NOI2009] 诗人小G
[HNOI2008] 玩具装箱
[NOI2019] 回家路线
[ARC066F] Contest with Drinks Hard