区间dp-拓扑排序种类数
https://vjudge.net/contest/311202#problem/L
之前在CF上做过类似的题，所以这次就被这种思维带过去了
后来看题解知道这题可以用到区间dp
一个排列，对每个元素给定le[i]和ri[i],表示[le[i],ri[i]]内的元素都大于等于p[i],而le[i]-1和ri[i]+1的元素都小于
p[i]
这有点像之前的CF上的线段树的题，但是可以用到区间dp,因为在区间[le,ri]内最小的元素的两边界就是le[i],ri[i]
然后就可以把一部分的元素丢到左边
得到dp[le,ri]=dp[le,minpos-1]*dp[minpos+1,ri]*C(ri-le,minpos-le);
腾讯泡池子943人在聊
投递美的集团等公司6个岗位 >