CFR 466 D. Increase Sequence ( Segment trick DP )

題意：
給陣列大小，目標高度，和陣列。可以對陣列進行任意次操作，將某個區間全部加一。前提是任意區間的左界不重複，右界也一樣。求方案數，使得陣列中所有元素為目標高度。

數據大小：
陣列大小 N ≤ 2000
目標高度 H ≤ 2000
陣列元素大小 A[ i ] ≤ 2000

解法：
dp[ i ][ j ] : 已考慮前 i 個元素，目前有 j 個區間左界已確定而右界不在 i 之前，此時的合法方案數。
有多少區間開著，就代表這次一定會至少加多少在當前考慮的元素上。因此只需要 j 為目標高度和當前元素的差的狀態來轉移，或者再 -1 後開啟新的區間做的轉移。轉移詳見代碼。

int N, H;
vi A;

void init(){
    cin >> N >> H;
    A = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
    for( int i = 0; i < N; ++i )
        if( H < A[ i ] ){
            cout << 0 << endl;
            exit( 0 );
        }
}

vvi dp;

void preprocess(){
    dp = vvi( N + 1, vi( N + 1 ) );
    dp[ 0 ][ 0 ] = 1;
    for( int i = 0; i < N; ++i )
        for( int j = 0; j <= i; ++j ){
            if( j + 1 == H - A[ i ] )
                ( dp[ i + 1 ][ j ] += dp[ i ][ j ] ) %= MOD7, // single element
                ( dp[ i + 1 ][ j + 1 ] += dp[ i ][ j ] ) %= MOD7, // add new segment
                ( dp[ i + 1 ][ j ] += 1LL * j * dp[ i ][ j ] ) %= MOD7; // close one segment, then add new segment
            if( j == H - A[ i ] )
                ( dp[ i + 1 ][ j - 1 ] += 1LL * j * dp[ i ][ j ] % MOD7 ) %= MOD7, // close one segment
                ( dp[ i + 1 ][ j ] += dp[ i ][ j ] ) %= MOD7; // do nothing
        }
}

void solve(){
    cout << dp[ N ][ 0 ] << endl;
}