题目描述

Description

Input

Output

Sample Input

4
1701 1702 1703 1704

Sample Output

8

HINT

题目分析

区间DP
f[i][j][0/1] 表示区间i~j的队形符合要求，并且上一次插在区间左边/右边的方案数

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,mod=19650827;
int a[1100],f[1020][1020][3];
int main()
{   
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) f[i][i][0]=1;
    for(int len=1;len<=n;len++)
        for(int l=1,r;(r=l+len)<=n;l++)
        {
            if(a[l]<a[l+1]) f[l][r][0]+=f[l+1][r][0]; 
            if(a[l]<a[r])   f[l][r][0]+=f[l+1][r][1];
            if(a[r]>a[l])   f[l][r][1]+=f[l][r-1][0];
            if(a[r]>a[r-1]) f[l][r][1]+=f[l][r-1][1];
            f[l][r][0]%=mod,f[l][r][1]%=mod;
        }
    printf("%d",(f[1][n][0]+f[1][n][1])%mod);
    return 0;
}