Codeforces 479E Riding in a Lift(dp)

Codeforces 479E Riding in a Lift(dp)

題目鏈接：Codeforces 479E Riding in a Lift

題目大意：有一棟高N層的樓，有個無聊的人在A層，他喜歡玩電梯，每次會做電梯到另外一層。但是這棟樓裡有個秘

密實驗室在B層，所以每次他移動的時候就有了一個限制，x為當前所在層，y為目標層，|x - y| < |x - b|。問說移動K次

後，有多少不同的路徑。

解題思路：dp[i][j]表示在第i步到達j層有多少種不同的路徑，dis = abs(j-B) - 1，那麼在[j-dis,j+dis]這個范圍都能被轉

移，除了j。那麼轉移方程就很好寫了。

但是直接轉移的話復雜度有點高，因為轉移的范圍是成段的，所以我們可以利用數組維護區間和的方式取優化。每次對

一個區間l，r加上某個值v的時候，等於在l處+v，r+1處-v，最後處理的時候每個位置的准確值即為數組的前綴和。

#include 
#include 
#include 
#include 

using namespace std;

const int maxn = 5005;
const int mod = 1e9 + 7;

int N, A, B, K, dp[maxn][maxn];

void add (int idx, int l, int r, int d) {
    dp[idx][l] = (dp[idx][l] + d) % mod;
    dp[idx][r] = (dp[idx][r] - d + mod) % mod;
}

int main () {
    scanf("%d%d%d%d", &N, &A, &B, &K);

    dp[0][A] = 1;
    for (int i = 0; i < K; i++) {
        for (int j = 1; j <= N; j++) {
            if (j == B) continue;
            int x = abs(j - B) - 1;
            add(i+1, max(j-x, 1), j, dp[i][j]);
            add(i+1, j+1, min(j+x+1, N + 1), dp[i][j]);
        }

        int mv = 0;
        for (int j = 1; j <= N; j++) {
            mv = (mv + dp[i+1][j]) % mod;
            dp[i+1][j] = mv;
        }
    }

    int ans = 0;
    for (int i = 1; i <= N; i++)
        ans = (ans + dp[K][i]) % mod;
    printf("%d\n", ans);
    return 0;
}