感谢所有AC

传送门

思路

     区间DP。定义状态 f( i , j ) 为从 i 到 j 这个队的方案数， 显然这个状态由 f( i+1 , j ) 和 f( i , j-1 ) 转移得来（即新入队的人从左边进或者从右边进）。但是在接下来的推导中发现，这样定义状态给转移带来很大的麻烦，既要考虑新人左进队，又要考虑新人右进队，且转移时还需要考虑前面的状态的进队次序，所以需要重新定义状态。

    由于进队的方式只有左进右进，可以给原状态增加一个维度，以 f( i , j, 0 ) 为新人左近的方案数，f( i , j, 1 )为新人右进的方案数，那么在转移中前面的状态的进队方式也变得明了，状态方程易得。

代码

#include
#define mod 19650827
using namespace std;
int n, h[2007], f[2007][2007][2];
int main(void)
{
	ios::sync_with_stdio(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> h[i];
	for (int i = 1; i <= n; i++)
		f[i][i][0] = f[i][i][1] = 1;
	for (int L = 1; L < n; L++)
		for (int i = 1, j = i + L; j <= n; i++, j++)
		{
			if (h[i] < h[i + 1])
				f[i][j][0] += f[i + 1][j][0] % mod;
			if (h[i] < h[j] && i + 1 != j)
				f[i][j][0] += f[i + 1][j][1] % mod;
			if (h[j] > h[i])
				f[i][j][1] += f[i][j - 1][0] % mod;
			if (h[j] > h[j - 1] && j - 1 != i)
				f[i][j][1] += f[i][j - 1][1] % mod;
		}
	cout << (f[1][n][0] + f[1][n][1]) % mod << '\n';
	return 0;
}