题目分析

不是很难的区间 dp，用 l[i][j] 表示 i 到 j 这端最后插入的是 a[i] 的方案数,r[i][j] 则表示 i 到 j 这端最后插入的是 a[j] 的方案数，就很容易推出状态转移方程：

l[i][j]=l[i+1][j](a[i+1]>a[i])+r[i+1][j](a[j]>a[i]);
r[i][j]=l[i][j-1](a[i]<a[j])+r[i][j-1](a[j-1]<a[j]);

然后初始化是 l[i][i]=1（或者 r[i][i]=1; 但是不可以两个都等于 1，不然会重复计算）

代码

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
int n,a[1005],mod=19650827;
int l[1005][1005],r[1005][1005];
int main()
{
    int i,j;
    n=read();
    for(i=1;i<=n;i++)a[i]=read();
    for(i=1;i<=n;i++)l[i][i]=1;
    for(i=n;i>=1;i--)
        for(j=i+1;j<=n;j++){
        if(a[i+1]>a[i])l[i][j]+=l[i+1][j];
        if(a[j]>a[i])l[i][j]+=r[i+1][j];
        l[i][j]%=mod;
        if(a[j]>a[i])r[i][j]+=l[i][j-1];
        if(a[j]>a[j-1])r[i][j]+=r[i][j-1];
        r[i][j]%=mod;
    }
    printf("%d",(l[1][n]+r[1][n])%mod);
    return 0;
}