CFR 479 E. Riding in a Lift ( Prefix Sum Trick DP )

Problem - 479E - Codeforces
題意：
給 N, A, B, K，代表有幾層樓，初始在哪層，哪層是禁止樓層，要轉移多少次。由 x 轉移到 y 是合法的若且唯若 | x - y | < | x - B |。求轉移 K 次，能有多少種不同的移動路徑，取其餘數。
解法：
dp[ i ][ j ] : 已轉移 i 次，最後一次在第 j 層樓時的方案數。
如果樸素轉移，會變成 O( N ^ 3 ) 的算法。但仔細想想，需要考慮的狀態是連續的，需要知道的只是分別向上與向下可移動最遠距離的 dp值的連續區間和。因此一邊做動態規劃，一邊動態維護 dp 值的前綴和。特別要注意處理禁止樓層的部分，稍有不慎就掰了。

int N, A, B, K;

void init(){
    cin >> N >> A >> B >> K;
}

vvi dp;
vvi pdp;

void preprocess(){
    dp = vvi( K + 1, vi( N + 1 ) );
    dp[ 0 ][ A ] = 1;
    pdp = vvi( K + 1, vi( N + 1 ) );
    for( int i = A; i <= ( A < B ? B - 1 : N ); ++i )
        pdp[ 0 ][ i ] = 1; // pdp[ k ][ i ] : prefix sum [ 0 .. i ]
    for( int i = 1; i <= K; ++i )
        for( int j = 1; j <= N; ++j ){
            if( j < B )
                dp[ i ][ j ] = ( 1LL * pdp[ i - 1 ][ j - 1 ]
                             +   pdp[ i - 1 ][ j + ( B - j - 1 ) / 2 ] - pdp[ i - 1 ][ j ] ) % MOD7;
            else if( B < j )
                dp[ i ][ j ] = ( 1LL * pdp[ i - 1 ][ N ] - pdp[ i - 1 ][ j ]
                             +   pdp[ i - 1 ][ j - 1 ] - pdp[ i - 1 ][ j - ( j - B - 1 ) / 2 - 1 ] ) % MOD7;
            pdp[ i ][ j ] = ( pdp[ i ][ j - 1 ] + dp[ i ][ j ] ) % MOD7;
        }
}

void solve(){
    int ans = 0;
    for( int i = 1; i <= N; ++i )
        ( ans += dp[ K ][ i ] ) %= MOD7;
    cout << ( ans + MOD7 ) % MOD7 << endl;
}