分析:根据它放人的规则,合唱队形从安排第一个人开始一定都会是一段连续的区间,所以考虑区间(DP).设(f[i][j])表示安排好理想队形的([i,j])时的方案数.
但是发现转移的时候需要知道上一次放的是哪一个数,所以拓展一维状态(f[i][j][0/1])表示安排好理想队形的([i,j])且当前放(a_i/a_j)时的方案数.
转移就不写了.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int mod=19650827;
const int N=1005;
int a[N];ll f[N][N][2];
int main(){
int n=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=n;++i){
f[i][i][0]=f[i][i][1]=1;
f[i][i+1][0]=(a[i]<a[i+1]);
f[i][i+1][1]=(a[i+1]>a[i]);
}
for(int len=3;len<=n;++len){
for(int i=1;i+len-1<=n;++i){
int j=i+len-1;
if(a[i]<a[i+1])f[i][j][0]=(f[i][j][0]+f[i+1][j][0])%mod;
if(a[i]<a[j])f[i][j][0]=(f[i][j][0]+f[i+1][j][1])%mod;
if(a[j]>a[i])f[i][j][1]=(f[i][j][1]+f[i][j-1][0])%mod;
if(a[j]>a[j-1])f[i][j][1]=(f[i][j][1]+f[i][j-1][1])%mod;
}
}
printf("%lld
",(f[1][n][0]+f[1][n][1])%mod);
return 0;
}