单调栈(笛卡尔树 区间DP)
【转载】作者:GuxueAkioi学习之用,为防丢失,故此转载,万望见谅,若有侵权,联系删除。题意:一开始有一个长度为 n 的未知排列。给出一个序列 a,其中 a[i] 表示单调栈在第 i 个数入栈后的 size 大小,a[i] = -1 表示 size 大小未知,根据序列 a 输出可能的初始排列的方案数。答案对 1e9+7 取模。规模:T组数据,T<=20,1<=n<=100。分析:首先考虑没有-1的情况,根据单调栈的性质我们不难发现最右边的 size