BZOJ-1996: [Hnoi2010]chorus 合唱队（

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1996

区间DP，注意len=2的处理不要重复即可。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std ;
 
#define rep( i , x , y ) for ( int i = x ; i <= y ; ++ i )
 
const int maxn = 1010 ;
const int mod = 19650827 ;
 
void update( int &N , int delta ) {
        ( N += delta ) %= mod ;
}
 
int dp[ maxn ][ maxn ][ 2 ] , n , a[ maxn ] ;
 
int main(  ) {
        scanf( "%d" , &n ) ;
        rep( i , 1 , n ) scanf( "%d" , a + i ) ;
        memset( dp , 0 , sizeof( dp ) ) ;
        rep( i , 1 , n ) dp[ i ][ i ][ 0 ] = 1 ;
        rep( i , 2 , n ) rep( j , 1 , n - i + 1 ) {
               int l = j , r = j + i - 1 ; 
               update( dp[ l ][ r ][ 0 ] , dp[ l + 1 ][ r ][ 0 ] * ( a[ l ] < a[ l + 1 ] ) ) ;
               update( dp[ l ][ r ][ 0 ] , dp[ l + 1 ][ r ][ 1 ] * ( a[ l ] < a[ r ] ) ) ;
               update( dp[ l ][ r ][ 1 ] , dp[ l ][ r - 1 ][ 0 ] * ( a[ r ] > a[ l ] ) ) ;
               update( dp[ l ][ r ][ 1 ] , dp[ l ][ r - 1 ][ 1 ] * ( a[ r ] > a[ r - 1 ] ) ) ;
        }
        printf( "%d\n" , ( dp[ 1 ][ n ][ 0 ] + dp[ 1 ][ n ][ 1 ] ) % mod ) ;
        return 0 ; 
}