DP的优化总结

一、预备知识

二、优化方法

1. 利用决策单调性

2. 分治优化

相关文章:post1

3. 单调队列

4. 斜率优化

相关文章: bzoj1492 [NOI2007]货币兑换Cash

5. 凸包优化(Convex Hull Trick)

相关文章:Convex hull trick

6. 凸包优化2

相关文章: post2

7. Knuth优化

相关文章:1 2

三、题目

凸包优化(CHT)

  1. BZOJ 1701-Cow School Solution-Video
  2. SPOJ-APIO2010 Commando
  3. SPOJ-TRAKA
  4. SPOJ-BAABO
  5. SPOJ-ACQUIRE
  6. SPOJ-NKLEAVES
  7. cf91e-SkyScrapers (+Data Structures)
  8. cf311b Cats Transport
  9. cf660f Bear and Bowling 4
  10. cf319c Kalila and Dimna in the Logging Industry
  11. cf631e Product Sum
  12. cf455e Function
  13. cf536c Tavas and Pashmaks
  14. cf377e Cookie Clicker
  15. cf91e Igloo Skyscraper
  16. Jump mission | CodeChef
  17. Contest Page | CodeChef

Knuth 优化

  1. Spoj-BRKSTRNG
  2. UVa10003-Cutting Sticks
  3. UVa10304
  4. Order-Preserving Codes - gym100212C
  5. UVa12057
  6. UVa-12836

分治优化

  1. cf321e Ciel and Gondolas
  2. hr-Guardians of the Lunatics
  3. Chef and Bitwise OR Operation | CodeChef
  4. SPOJ-NKLEAVES
  5. hr-mining
  6. Bicolored Horses
  7. UVa12524
  8. cf673e Levels and Regions
  9. ARC 067D

斜率优化

  1. BZOJ 1597 [Usaco2008 Mar]土地购买
  2. BZOJ 3675 [APIO 2014]序列分割
  3. BZOJ 1010 [HNOI2008]玩具装箱toy
  4. BZOJ 3437 小P的牧场
  5. BZOJ 3156 防御准备
  6. BZOJ 1096 [ZJOI2007]仓库建设
  7. BZOJ 1911 APIO 2010 Commando
  8. BZOJ 4518 [SDOI2016] 征途
  9. HDU 3507
  10. HDU 3401
  11. HDU 2191
  12. HDU 5956 The Elder

平衡树维护动态凸包

  1. cf70d
  2. BZOJ 2300(HAOI2011)防线修建
  3. BZOJ 1492 货币兑换Cash
  4. HDU 5127 Dogs’ Candies

参考文章:

  1. Dynamic programming with convexity, concavity and sparsity
  2. 《算法艺术与信息学竞赛》p149。
  3. 1D1D动态规划优化初步
  4. 动态规划算法的优化技巧-毛子青
  5. dp优化-个人对dp优化的理解
  6. Dynamic Programming Optimizations
  7. 斜率优化 二

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Gym 100610A】Alien Communication Masterclass

    Andrea is a famous science fiction writer, who runs masterclasses for her belove...

    饶文津
  • 【POJ1083】 Moving Tables (并行的搬运)

    房间1和2,3和4,...,399和400共用一节走廊,有q次从房间li到ri的搬运桌子,一次搬运10分钟。两个搬运如果走廊有重叠部分,则必须一个结束后再执行另...

    饶文津
  • 【hdu6188】Duizi and Shunzi(贪心)

    2017ACM/ICPC广西邀请赛 重现赛1007 Duizi and Shunzi

    饶文津
  • windows server 设置内网访问共享文件

    1011419860
  • Go语言test之类方法测试

    Go语言提供了完善的单元测试支持,开发人员可以方便的编写测试代码,保证自己代码的质量。在目前的例子中,一般看到都是普通函数的例子。下面我将举类方法的测试例子来展...

    李海彬
  • 简单二维CAD图纸(使用javascript多快好省绘制)

    [题引]:君子性非异也,善假于物也。javascript本身不能绘制CAD图纸,但借助第三方库就可以绘制一些简单的二维图纸了。到被戏称为“全球最大的同性...

    周星星9527
  • LeetCode 11:用递归和动规解决正则表达式匹配

    给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

    帅地
  • 从0打卡leetcode之day11--正则表达式匹配

    给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

    帅地
  • 网络编程懒人入门(一):快速理解网络通信协议(上篇)

    论坛和群里常会有技术同行打算自已开发IM或者消息推送系统,很多时候连基本的网络编程理论(如网络协议等)都不了解,就贸然定方案、写代码,显得非常盲目且充满技术风险...

    JackJiang
  • Django踩坑笔记

    V站CEO-西顾

扫码关注云+社区

领取腾讯云代金券