Codeforces Round #274 (Div. 2) E题：Riding in a Lift（DP）_html/css_WEB-ITnose

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64const LL mod=1e9+7;LL dp[6000], sum[3][6000];int main(){    LL n, a, b, k, i, j;    while(scanf("%I64d%I64d%I64d%I64d",&n,&a,&b,&k)!=EOF)    {        memset(dp,0,sizeof(dp));        memset(sum,0,sizeof(sum));        dp[a]=1;        for(i=a;i<=n;i++)            sum[0][i]=1;        for(i=1;i<=k;i++)        {            sum[i&1][0]=0;            for(j=1;j<=n;j++)            {                if(j<b)                {                    dp[j]=(sum[i+1&1][(j+b-1)/2]+mod-dp[j])%mod;                }                else if(j>b)                {                    dp[j]=(sum[i+1&1][n]+mod-sum[i+1&1][(j+b)/2]+mod-dp[j])%mod;                }                sum[i&1][j]=(sum[i&1][j-1]+dp[j])%mod;                //printf("%I64d ",dp[j]);            }            //puts("");        }        printf("%I64d\n",sum[k&1][n]);    }    return 0;}