记录编号	148392	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 合唱队	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.131 s
提交时间	2015-02-11 19:55:27	内存使用	8.10 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x3fffffff;
//==============struct declaration==============

//==============var declaration=================
const int MAXN=1010;
const int MOD=19650827;
int f[MAXN][MAXN][2];
int n,A[MAXN];
//==============function declaration============

//==============main code=======================
int main()
{  
#define FILE__
#ifdef FILE__
  freopen("chorusu.in","r",stdin);
  freopen("chorusu.out","w",stdout);
#endif  
  scanf("%d",&n);memset(f,0,sizeof(f));
  for(int i=1;i<=n;i++)
    scanf("%d",A+i);
  for(int i=1;i<n;i++)
    if (A[i]<A[i+1])
      f[i][i+1][1]=f[i][i+1][0]=1;
  for(int length=3;length<=n;length++)//0 represent the lastest is the first number,1 represent the lastest it the last number.
    for(int st=1;st+length-1<=n;st++){
       int ed=st+length-1;
       if (A[st]<A[st+1]) f[st][ed][0]+=f[st+1][ed][0];
       if (A[st]<A[ed]) f[st][ed][0]+=f[st+1][ed][1];
       if (A[ed]>A[st]) f[st][ed][1]+=f[st][ed-1][0];
       if (A[ed]>A[ed-1]) f[st][ed][1]+=f[st][ed-1][1];
       f[st][ed][1]=f[st][ed][1]%MOD;
       f[st][ed][0]=f[st][ed][0]%MOD;
    }
  printf("%d\n",(f[1][n][1]+f[1][n][0])%MOD);
  return 0;
}
//================fuction code====================