不是题解 违规紫衫
设 $b_{i,j}$ 是必须包含端点的区间[i,j]的上升子序列数量, $c_{i,j}$ 是必须包含端点的区间[i,j]的下降子序列数量, $f_i,j$ 是以 i 为左端点, 并且山峰高度必须大于$a_j$的山峦数量. 状态转移方程是 $f_{i,j}=\sum_{k=i+2}^n(\sum_{l=i+1}^{k-1}[a_l>a_j]b_{i,l}c_{l,k}(f_{k+1,l}+1))$. 答案是 $\sum_{i=1}^nf_{i,0}$
$b_{i,j}$和$c_{i,j}$是这么处理的:

for(int i = 1; i <= n; i++) {
		for(int j = i; j <= n; j++) {
			if(i==j)b[i][j]=1,c[i][j]=1;
			else {
				if(a[i]>=a[j])b[i][j]=0;
				else b[i][j]=1;
				if(a[i]<=a[j])c[i][j]=0;
				else c[i][j]=1;
				for(int k = j-1; k > i; k--) {
					if(b[i][j]&&(a[k]<a[j]&&a[i]<a[k]))b[i][j]+=b[i][k];
					if(c[i][j]&&(a[k]>a[j]&&a[i]>a[k]))c[i][j]+=c[i][k];
				} 
			}
		}
	}

按这个方法写样例1和2没问题, 样例3输出13162.
找了好久,还是没看出哪有问题, 求大佬解答, 必关.