原题链接

这道题相对简单，注意到对于给定的最终队列，最后一个加入的人要么在队首要么在队尾，假设其长度为n，则其可能由其两个长度为n-1的子区间队列转化而来，状态转移时分4类判断可能由哪些状态转移而来，情况数量累加即可。

使用三维的状态存储数组，便于状态分类和转移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<algorithm>
#include<cstring>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
// P3205合唱队
// https://www.luogu.com.cn/problem/P3205
const int N=1010,mod=19650827;

int dp[N][N][2]; // dp[i][j][k]表示编号从i到j的区间，k==0为最后一次插入到队首的情况，k==1是插入到队尾
int n,h[N];

int main(){ 
    fastIO
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=n;i++) dp[i][i][0]=1; // 避免重复计算

    for(int l=2;l<=n;l++){
        for(int i=1;i+l-1<=n;i++){
            int j=i+l-1;
            if(h[i]<h[i+1]) dp[i][j][0]=(dp[i][j][0]+dp[i+1][j][0])%mod; // 最后一次是插入队首，从最后一次插入队首的状态转移过来
            if(h[i]<h[j]) dp[i][j][0]=(dp[i][j][0]+dp[i+1][j][1])%mod;
            if(h[j]>h[i]) dp[i][j][1]=(dp[i][j][1]+dp[i][j-1][0])%mod;
            if(h[j]>h[j-1]) dp[i][j][1]=(dp[i][j][1]+dp[i][j-1][1])%mod;
        }
    }
    cout<<(dp[1][n][1]+dp[1][n][0])%mod<<endl; // 两类情况相加

    return 0;
}