一些 dp 状态 & 技巧

  • fxf_x 表示达到状态 xx 的期望,答案即为 fneedf_{need}

  • fx,yf_{x,y} 表示从状态 xx 转到状态 yy 的期望,求答案的时候加起来;

  • 遇到求 ()x()^x 的时候直接二项式定理设多个 dp 数组,或者考虑 xx 个人同时进行一样的操作;

  • 考虑折线图/笛卡尔树;

  • 箭头 dp:

    dpi,jdp_{i,j} 表示前 ii 个元素,有 jj 段。转移考虑新建段、加入某段的左边/右边、合并两段。

    例题:

  • 非负整数划分 dp:

    非负整数 nn 划分成 mm 个带标号非负整数的方案数。

    fi,jf_{i,j} 表示 jj 划分成 ii 个带标号非负整数的方案数,那么有 f,0=1f_{*,0}=1。转移考虑有多少个 1\ge 1 的数:

    fi,j=k=1min(i,j)(ik)fk,jkf_{i,j}=\sum\limits_{k=1}^{\min(i,j)}\binom{i}{k}f_{k,j-k}

  • 折线优化:

    考虑某些形如 fi,j=max(fi1,j+x+w1,fi1,j+y+w2)f_{i,j}=\max(f_{i-1,j+x}+w_1,f_{i-1,j+y}+w_2) 这样的只和上一列有关的 dp,可以猜想并且经常有:

    存在某个 kk 满足 fi,j={fi1,j+x+w1jkfi1,j+y+w2j>kf_{i,j}=\begin{cases}f_{i-1,j+x}+w_1&j\le k\\f_{i-1,j+y}+w_2&j>k\end{cases}

    例题:

  • 在 dfs 序上 dp:【2025NOI模拟赛19】b酱的果子