Codeforces Round #274 Div. 2 E. Riding in a Lift

題目鏈接：http://codeforces.com/contest/479/problem/E

題意

輸入n,a,b,k
一棟樓有n層，起點在a層，b層不能去
如果想乘電梯從x層去y層必須滿足|x-y|<|y-b|
求從起點a出發總共經過k層樓的方法數

解法

用動態規劃解法
dp[i][j]表示走了i層樓,最後停在了j樓

• dp[i][y]=dp[i][y]+dp[i-1][x](|x-y|<|y-b| && 1<=x<=n)`
• dp[i][y]=dp[i][y]-dp[i-1][y] (不能從y層到y層)

直接這樣時間複雜度太高
由於滿足條件的x肯定是連續的
所以維護前綴和優化

typedef long long LL;
const int N=5005;
const LL mod=1e9+7;
LL dp[N][N];
inline void add(LL& x,LL y) {
    x+=y;
    x%=mod;
}
void init(int n,int a) {
    memset(dp,0,sizeof(dp));
    for(int i=a;i<=n;i++) {
        dp[0][i]=1;
    }
}
void solve() {
    int n,a,b,c;
    cin>>n>>a>>b>>c;
    init(n,a);
    for(int i=1;i<=c;i++) {
        for(int j=1;j<=n;j++) {
            if(j==b) continue;
            int l=0;
            int r=(j+b-1)/2;
            if(j>b) {
                l=(b+j)/2;
                r=n;
            }
            LL s=dp[i-1][r]-dp[i-1][l];
            s-=(dp[i-1][j]-dp[i-1][j-1]);
            s=(s%mod+mod)%mod;
            add(dp[i][j],s);
        }
        for(int j=1;j<=n;j++) {
            add(dp[i][j],dp[i][j-1]);
        }
    }
    cout<<dp[c][n]<<endl;
}