bzoj1996 [Hnoi2010]chorus 合唱队

Description

Input

Output

Sample Input

4
1701 1702 1703 1704

Sample Output

HINT

正解：区间$DP$。

比较简单的区间$DP$，但是因为是$HNOI$所以必须留版面。。

设$f[0][l][r]$表示已经处理完区间$l,r$之间的人，最后一个人放在左边的方案数，$f[1][l][r]$表示已经处理完区间$l,r$之间的人，最后一个人放在右边的方案数。然后直接大力转移就行了。

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <cmath>
 9 #include <queue>
10 #include <stack>
11 #include <map>
12 #include <set>
13 #define inf (1<<30)
14 #define il inline
15 #define RG register
16 #define ll long long
17 #define rhl (19650827)
18  
19 using namespace std;
20  
21 ll f[2][1010][1010],a[1010],n;
22  
23 il int gi(){
24     RG int x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
25     if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;
26 }
27  
28 il void work(){
29     n=gi(),a[0]=inf;
30     for (RG int i=1;i<=n;++i) a[i]=gi(),f[0][i][i]=f[1][i][i]=1,f[0][i-1][i]=f[1][i-1][i]=(a[i-1]<a[i]);
31     for (RG int k=3;k<=n;++k)
32     for (RG int l=1;l+k-1<=n;++l){
33         RG int r=l+k-1;
34         f[0][l][r]=(a[l]<a[l+1])*f[0][l+1][r]+(a[l]<a[r])*f[1][l+1][r];
35         f[1][l][r]=(a[l]<a[r])*f[0][l][r-1]+(a[r-1]<a[r])*f[1][l][r-1];
36         if (f[0][l][r]>=rhl) f[0][l][r]-=rhl;
37         if (f[1][l][r]>=rhl) f[1][l][r]-=rhl;
38     }
39     printf("%lld
",(f[0][1][n]+f[1][1][n])%rhl);
40     return;
41 }
42  
43 int main(){
44     work();
45     return 0;
46 }