可以操作任意多次。考虑 dp。
设 \(dp_i\) 表示考虑前 \(i\) 个位置之后，强制最终留下第 \(i\) 个位置上的数的方案数，转移时枚举前面的位置 \(j\)，对于合法的决策 \(j\)，显然需满足 \(\forall k\in(j,i)\)，\(a_k>a_i\) 或 \(a_k>a_j\)。
显然可以提前预处理出每个位置 \(i\) 向前第一个比 \(a_i\) 小的数的下标 \(la_i\)，则决策 \(k\in[la_i,i)\) 一定合法；对于决策 \(k\in[1,la_i)\)，不难发现只有位于从 \(1\) 到 \(la_i-1\) 组成的单调递增的单调栈内的下标才合法。
于是可以在 dp 过程中顺便维护 \(sum_i\) 表示 \(\sum_{j=1}^i dp_j\)，\(f_i\) 表示前 \(i\) 项组成的单调栈内的 \(dp\) 值之和，即可做到 \(O(n)\) 转移。
转操作至局面充要。
标签：Collapse,la,Edu160D,CF,dp,Array,单调,栈内 From： https://www.cnblogs.com/ydtz/p/17916059.html