记忆化搜求调

#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
int n;
int a[2020];
const int mod=19650827;
int dp[2020][2020][2];  //dp[i][j][k]表示形成从i~j的队列的方法数,k==0表示左端点最后进来，k==1表示右端点
int dfs(int l,int r,bool k)
{
    if(l+1==r) return 1;
    if(dp[l][r][k]) return dp[l][r][k];
    //拆分方法数：考虑最后一个进队的在头还是在尾
    int x=0,y=0;
    if(k==0)
    {
        if(a[l+1]>a[l]) x=dfs(l+1,r,0)%mod;  //l是最后进来的，若l+1是次后进来的，l必须比l+1小才能放最前面
        if(a[r]>a[l]) y=dfs(l+1,r,1)%mod;
    }
    if(k==1)
    {
        if(a[l]<a[r]) x=dfs(l,r-1,0)%mod;  //r最后进来，若l是次后进来的，r必须比它大才能插到尾部
        if(a[r-1]<a[r]) y=dfs(l,r-1,1)%mod;
    }
    return dp[l][r][k]=(x+y)%mod;
}
main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cout<<(dfs(1,n,0)+dfs(1,n,1))%mod;
}