「BZOJ1996」[HNOI2010]chorus 合唱队

Description

为了在即将到来的晚会上有更好的演出效果,作为AAA合唱队负责人的小A需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共NN个人,第ii个人的身高为HiH_i(1000\leqH_i\leq2000),并已知任何两个人的身高都不同。假定最终排出的队形是AA个人站成一排,为了简化问题,小A想出了如下排队的方式:他让所有的人先按任意顺序站成一个初始队形,然后从左到右按以下原则依次将每个人插入最终棑排出的队形中:

  • 第一个人直接插入空的当前队形中。

  • 对从第二个人开始的每个人,如果他比前面那个人高(HH较大),那么将他插入当前队形的最右边。如果他比前面那个人矮(HH较小),那么将他插入当前队形的最左边。

NN个人全部插入当前队形后便获得最终排出的队形。

例如,有66个人站成一个初始队形,身高依次为185018501900190017001700165016501800180017501750,

那么小A会按以下步骤获得最终排出的队形:

1850

1850 1900 因为 1900>18501900 > 1850

1700 1850 1900 因为 1700<19001700 < 1900

1650 1700 1850 1900 因为 1650<17001650 < 1700

1650 1700 1850 1900 1800 因为 1800>16501800 > 1650

1750 1650 1700 1850 1900 1800 因为 1750<18001750 < 1800

因此,最终排出的队形是 17501750165016501700170018501850, 1900190018001800

小A心中有一个理想队形,他想知道多少种初始队形可以获得理想的队形

Input

第一行一个正整数NN,表示总人数。
第二行是用空格隔开的NN个正整数,从左到右表示小A心中的理想队形:H1,H2,HnH_1,H_2,\cdots H_n。输入的数据保证1Hi20001\leq H_i\leq 2000且没有相同的HH值。

Output

仅包含一个数,表示从多少种初始队形出发能通过上述排队的方式获得输入种指定的小A心中的理想队形。答案要输出(mod19650827)\pmod{19650827}的值。

Sample Input

1
2
4
1701 1702 1703 1704

Sample Output

1
8

HINT

对于30%30\%的数据,满足1N1001\leq N\leq 100
对于100%100\%的数据,满足1N10001\leq N\leq 1000

Solution

fi,j,0f_{i,j,0}fi,j,1f_{i,j,1}表示区间[l,r][l,r]且左端或者右端的数是当前序列的最后一个数。
fi,i,0f_{i,i,0}fi,i,1f_{i,i,1}是等价的,所以为了防止重复,只有一个初始值为11
讨论从子区间里转移出来的大小关系。

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
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 1100;
const int p = 19650827;
void add(int &x, int v) {
x += v;
if(x >= p) x %= p;
}
int f[1100][1100][2];
int a[N], n;
int main() {
n = read();
for(int i = 1; i <= n; ++i) a[i] = read(), f[i][i][0] = 1;
for(int len = 2; len <= n; ++len) {
for(int i = 1; i + len - 1 <= n; ++i) {
int j = i + len - 1;
if(i < n && a[i] < a[i + 1])add(f[i][j][0], f[i + 1][j][0]);
if(i < n && a[i] < a[j])add(f[i][j][0], f[i + 1][j][1]);
if(j > 0 && a[j] > a[i])add(f[i][j][1], f[i][j - 1][0]);
if(j > 0 && a[j] > a[j - 1])add(f[i][j][1], f[i][j - 1][1]);
}
}
writeln((f[1][n][0] + f[1][n][1]) % p);
return 0;
}