f[i][j][0/1] 表示已经排出队形中的[i,j]，最后一个插入的人在[i,j]的i或j

 

枚举顺序一：

先枚举区间长度，再枚举区间左端点

 

枚举顺序二：

先倒序枚举区间左端点，再枚举区间右端点

 

初始化：

当长度为2时，转移方程中的j==i+1，i==j-1

令f[i][j]只累加一次，所以f[i][i][0]=1 或者是 f[i][i][1]=1都行

 

#include
     
      #include
      
       using namespace std;#define N 1001const int mod=19650827;int a[N];int f[N][N][2];void read(int &x){    x=0; char c=getchar();    while(!isdigit(c))  c=getchar();     while(isdigit(c)) { x=x*10+c-'0'; c=getchar();  }}int main(){    int n;    read(n);    for(int i=1;i<=n;++i) read(a[i]);    for(int i=1;i<=n;++i) f[i][i][1]=1;    int j;    for(int len=2;len<=n;++len)        for(int i=1;i+len-1<=n;++i)        {            j=i+len-1;            if(a[i]
       
        a[i]) f[i][j][1]+=f[i][j-1][0];            if(a[j]>a[j-1]) f[i][j][1]+=f[i][j-1][1];            while(f[i][j][0]>=mod) f[i][j][0]-=mod;            while(f[i][j][1]>=mod) f[i][j][1]-=mod;        }    int ans=f[1][n][0]+f[1][n][1];    if(ans>=mod) ans-=mod;    cout<
       
      
     

 

1996: [Hnoi2010]chorus 合唱队

Time Limit: 4 Sec  Memory Limit: 64 MB

Submit: 1891  Solved: 1232

[][][]

Description

Input

Output

Sample Input

4

1701 1702 1703 1704

Sample Output

8

HINT