持续更新——dp的一些技巧

共菜鸡笔者看的……会慢慢更新,也请看到的大佬留意一眼,指出不足。

  • 对于一些对部分点的二维(dp),状态从左上角继承而来时,对于一个点((x,y)),对它编号(x*m+y),按照这个顺序(dp),可以保证更新当前值之前前面的已经被更新。
  • 善于发掘题目的性质。对于一些一眼看上去没法(dp)的东西,观察题目条件,将无用的状态去除或者确定一种(dp)顺序之类,变成一个经典的(dp)模型。
  • (dp)柿子写完,观察其中有没有类似(i*j)项的东西,看是不是能够斜率优化。推柿子原则:(y)是所有与(j)有关的项,(k)(i*j)项中与(i)有关的部分,(x)(i*j)项中与(j)有关的部分,(b)是只与(i)有关的部分。
  • 斜率优化的时候,观察题目要求的是( ext{max/min})(b)项的(dp[i])的符号,这些是决定凸包方向的重要条件。
  • 斜率优化的时候特别留意决策单调性,如果斜率单调,我们可以做到(O(n))维护决策点;有一些不单调的(比如斜率),就要考虑其他维护决策点的方法。
  • 赋值初始值能不用( ext{memset})就不用……
  • (dp)前捋清方程,推柿子的时候千万注意符号,如果反了就完了

持续( ext{update……})

原文地址:https://www.cnblogs.com/h-lka/p/12820416.html