区间DP

区间DP：

显然是一个区间向左右拓展形成的下一个区间，具有包含关系，所以可以使用区间DP。

状态设计：

考虑和关路灯一样设计状态

因为不知道当前这个区间是从哪个区间拓展而来，即不知道这个区间最后一个进来的人站在了哪里

设\(f(i,j,0/1)\)代表区间\([i,j]\)的方案数，第三维为\(0\)代表站在左边，为\(1\)站在右边

\[f(i,j,0)=f(i+1,j,0) \times (h_i<h_{i+1})+f(i+1,j,1) \times h_i<h_j\]

\[f(i,j,1)=f(i,j-1,0) \times (h_j>h_{i})+f(i,j-1,1) \times (h_j>h_{j-1})\]

技巧：

  • 在区间DP，发现常规\(f(i,j)\)不太方便转移时，可能需要加一维\(0/1\)。

  • 对于if(....) opt[i][j]+=k的转移，可以写作opt[i][j]+=k*(....)