本文共 1761 字，大约阅读时间需要 5 分钟。

题目链接：

题目大意：

给出一栋n层的楼，初始在a层，b层不能去，每次走的距离必须小于当前位置到b的距离，问用电梯来回乱跑得到的序列有多少种。

题目分析：

• 定义状态dp[i][j]表示第i次乱跑跑到了j的方案数。
• 定义dis等于|j-b|
• 那么我们每次转移dp[i][j]能够转移到[j-dis,j+dis]
• 但是我们要把当前位置去掉，也就是修改两段，我们采取段首加值，段尾减值，然后通过求一遍前缀和得到每个点的值。能够将转移优化到$\mathcal{O}(n)$

  ---

AC代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #define MAX 5007using namespace std;typedef long long LL;LL dp[MAX][MAX];int n,a,b,k;const LL mod = 1e9+7;int main ( ){    while ( ~scanf ( "%d%d%d%d" , &n , &a , &b , &k ) )    {        memset ( dp , 0 , sizeof ( dp ) );        dp[0][a] = 1;        for ( int i = 0 ; i <= k ; i++ )        {            for ( int j = 1 ; j <= n ; j++ )            {                if ( j == b ) continue;                int d = abs ( j - b );                int l = max(j-d+1,1);                int r = min(j+d,n+1);                dp[i+1][l] += dp[i][j];                dp[i+1][l] %= mod;                dp[i+1][r] -= dp[i][j];                dp[i+1][r] %= mod;                if ( l <= j <= r )                {                    dp[i+1][j] -= dp[i][j];                    dp[i+1][j] %= mod;                    dp[i+1][j+1] += dp[i][j];                    dp[i+1][j+1] %= mod;                }            }            for ( int j = 1 ; j <= n ; j++ )            {                dp[i+1][j] += dp[i+1][j-1];                dp[i+1][j] %= mod;            }            /*cout << "i : " << i <<  endl;            for ( int j = 1 ; j <= n ; j++ )                cout << dp[i][j] << " ";            cout << endl;*/        }        LL ans = 0;        for ( int i = 1 ; i <= n ; i++ )        {            if ( i == b ) continue;            ans += dp[k][i];            ans %= mod;        }        ans = (ans+mod)%mod;        printf ( "%I64d\n" ,ans );    }}
       
      
     
    
   

转载地址：http://zqvjn.baihongyu.com/