这应该又是一道 HNOI 的普及 DP 吧。。。

可以发现，每次插入后都将是一个连续的区间，所以就是区间 DP 辣

设 \(f(i,j,0)\) 为区间 \([i,j]\) 最后一个推进 \(i\) 的方案数，\(f(i,j,1)\) 为最后一个推进 \(j\)。

\[ \begin{cases} f(i,j,0) = f(i + 1,j,0) + f(i + 1,j,1) & A_i < A_{i + 1}\;and\;A_i < A_j \\ f(i,j,1) = f(i,j - 1,1) + f(i,j - 1, 0) & A_r > A_{r - 1} \;and\;A_r > A_l \end{cases} \]

最终答案就是 \(f(1,n,0)+f(1,n,1)\)

边界条件只要将区间长度为 \(2\) 的情况特判下就行了。

#include 
    
     #include 
     
      const int Mod = 19650827;const int MaxN = 1000 + 5;int N;int A[MaxN], Dp[MaxN][MaxN][2];inline int read(){    register int x = 0;    register char ch = getchar();    while(!isdigit(ch)) ch = getchar();    while(isdigit(ch))    {        x = x * 10 + ch - '0';        ch = getchar();    }    return x;}int main(){    N = read();    for(int i = 1; i <= N; ++i) A[i] = read();    for(int len = 2; len <= N; ++len)    {        for(int l = 1; l + len - 1 <= N; ++l)        {            int r = l + len - 1;            if(len == 2)            {                if(A[l] < A[r]) Dp[l][r][0] = Dp[l][r][1] = 1;                continue;            }            if(A[l] < A[l + 1]) Dp[l][r][0] += Dp[l + 1][r][0];            if(A[l] < A[r]) Dp[l][r][0] += Dp[l + 1][r][1];            Dp[l][r][0] %= Mod;            if(A[r] > A[r - 1]) Dp[l][r][1] += Dp[l][r - 1][1];            if(A[r] > A[l]) Dp[l][r][1] += Dp[l][r - 1][0];            Dp[l][r][1] %= Mod;        }    }    printf("%d\n", (Dp[1][N][0] + Dp[1][N][1]) % Mod);    return 0;}