题目

BZOJ传送门= ̄ω ̄=
LUOGU传送门= ̄ω ̄=

题目描述

题目描述

输入格式

输入格式

输出格式

输出格式

样例输入

样例输出

题解

基础区间DP,要注意题意是前一个入队的人和当前的人比,不是队的右端和当前的人比……(窝就被坑了)。
所以我们设:$f[i,j,p]$(p=0或1)为区间为$[l,r]$,当前要把这个人插入到左端(p=0)或右端(p=1)时有多少种不同解。
然后$arr[i]$表示第i个人的高度
所以可以得到这个递推式:
$f[i,j,0]=f[i,j-1,0]×(arr[j]>arr[i])+f[i,j-1,1]×(arr[j]>arr[j-1])$
$f[i,j,1]=f[i+1,j,0]×(arr[i]<arr[i+1])+f[i+1,j,1]×(arr[i]<arr[j])$

注意!$f[i,i,0]=1,f[i,i,1]=0$!或者$f[i,i,1]=1,f[i,i,0]=0$也行!不然会重复计算!

代码: