常用DP技巧
前 \(i-1\) 个到前 \(i\) 个，在末尾加入（钦定了相对顺序）
以一个分界线（一般为最值），将序列分开，然后插入（一般为最值），两个子段互比
计数 DP 拆式子：有共同变量的不必每次枚举，提出来预处理，优化时间复杂度
思路
看到前缀最大值 \(\to\) 将最大值提出来 \(\to\) 左侧只有前缀最大，右侧后缀最大 \(\to\) 形似插板的计数DP
先做左侧，\(f_{i,x,y}\) 为已有 \([1,i]\)，前缀最大值为 \(x\) 个，已有 \(y\) 个上升索引，转移考虑插入 \(i\)
开头：\(f_{i,x,y}\to f_{i + 1, x + 1, y}\)
末尾：\(f_{i,x, y} \to f_{i + 1, x, y}\)
上升间隔：\(f_{i + 1, x, y}\leftarrow f_{i, x, y} \times y\)
下降间隔： \(f_{i + 1, x, y + 1} \leftarrow f_{i, x, y} \times (i - y - 1)\)
加上滚动数组，空间 \(O(n^2)\)，时间 \(O(n^3)\)
那么对于长度为 \(n\) 的答案
\[\begin{aligned}ans_n=\sum_{p=1}^{n}\sum_{i=0}^{p-1}\sum_{j=0}^{n-p}\sum_{x=0}^{p-1}\sum_{y=0}^{n-p}C^{p-1}_{n-1}\times f_{p-1,i,x}\times g_{n-p,j,y}\times a_{i+1}\times b_{j+1}\times c_{x+y+[p>1]}\end{aligned} \]由于前缀最大值之和左边有关，后缀最大值之和右边有关，发现 \(f_{p- 1,i, x}\times a_{i + 1}\) 只有 3 个变量不同，于是可以预处理合并这两项为 \(u_{p,x} = \sum_{i=0}^{p-1}f_{p-1, i, x} \times a_{i + 1}\)
类似的，处理出 \(v_{j, y}\)，于是：
\[\begin{aligned} ans_n=\sum_{p=1}^{n}\sum_{x=0}^{p-1}\sum_{y=0}^{n-p}C^{p-1}_{n-1}\times u_{p-1,x}\times v_{n - p, y} \times c_{x+y+[p>1]} \end{aligned} \]发现 \(u_{p-1, x}\times c_{x + y + [p>1]}\) 也可以同理合并为 \(w_{p, y}=\sum_{x=0}^{p-1}{u_{p-1,x}\times c_{x+y+[p>1]}}\)
\[\begin{aligned} ans_n = \sum_{p=1}^{n} \sum_{y=0}^{n - p} C_{n-1}^{p-1}\times w_{p-1,y} \times v_{n - p, y} \end{aligned} \] 标签：begin,前缀,--,sum,CF1988F,times,Heartbeat,aligned,最大值 From： https://www.cnblogs.com/sukiqwq/p/18526368/CF1988F