codeforces 479E E. Riding in a Lift(dp+ 세그먼트 수정 최적화)

제목 링크:

codeforces 479E

제목 대의:

n층의 건물을 제시하는데 처음에 a층에 있었고 b층은 갈 수 없었다. 매번 걷는 거리는 현재 위치에서 b까지의 거리보다 작아야 한다. 엘리베이터로 왔다갔다하며 얻은 서열이 몇 가지냐고 물었다.

제목 분석:

정의 상태 dp[i][j]는 i차 제멋대로 j까지 뛰는 방안의 수를 나타낸다.

정의dis는 |j-b|

와 같다

그러면 우리는 매번 dp[i][j]를 [j-dis, j+dis]

로 옮길 수 있다.

그러나 우리는 현재 위치를 없애야 한다. 즉, 두 단락을 수정해야 한다. 우리는 단락의 첫 번째 값, 단락의 끝 값을 줄이고 접두사를 한 번 구하고 각 점의 값을 얻는다.O(n)로 전환 최적화 가능

AC 코드:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define MAX 5007

using 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
" ,ans );
    }
}