CFR 637 D. Running with Obstacles ( DP, Reverse Thinking )

Problem - D - Codeforces

題意：
初始時在 x = 0，要到 x = M，一路上會有若干個地雷。有兩種移動方式，跑步可以一次跑無窮遠，但不能越過地雷，跳躍可以越過地雷，但必須先跑連續至少 S 格，才能進行一次至多 D 格移動的跳躍。所有移動都只能向右。求是否存在方案，若有則輸出方案。

數據範圍：
地雷數 1 ≤ N ≤ 2e5
終點座標 2 ≤ M ≤ 1e9
能量定數，跳躍定數，1 ≤ S, D ≤ 1e9

解法：
首先注意到，一定只會從某個地雷前一個格子進行跳躍，也只會在某個地雷後一個格子著地，這樣一定是最好的。但如果從前面的地雷考慮，就必須試著轉移到後面每一個地雷後，因為不能確定哪個地雷會不會是死路。但如果逆著想，也就是從最後一個地雷後一格著地開始逆推回來，就只需要轉移到可轉移且與當前最近的地雷前一格。可以反證這是正確的，因為如果跳到最近的地雷的策略會丟失解，且有一個更前面的地雷轉移過來是對的，那代表有個地雷可以跳到某個地方，卻無法跳到之間有非地雷的某個地，而這是與定義矛盾的。

時間 / 空間複雜度：
類似爬行，因此 O( N )

需要注意：
記得找到第一個轉移點就要 break，不然會變 O( N ^ 2 )
RUN 不能 0 步

int N, M, S, D;
vi A;

void init(){
    cin >> N >> M >> S >> D;
    A = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
}

vi dp;

void preprocess(){
    A.emplace_back( -1 );
    ++N;
    sort( A.begin(), A.end() );
    dp = vi( N, -1 );
    for( int i = N - 1, cnt = 0; 0 < i; ){
        int ni = -1;
        for( int j = i - 1; 0 <= j; --j ){
            int run = A[ j + 1 ] - A[ j ] - 2;
            int jump = A[ i ] - A[ j + 1 ] + 2;
            if( S <= run and jump <= D ){
                ni = j,
                dp[ j ] = i;
                break;
            }
        }
        if( ni == -1 )
            cout << "IMPOSSIBLE" << endl,
            exit( 0 );
        i = ni;
    }
}

void solve(){
    for( int i = 0; ~dp[ i ]; i = dp[ i ] )
        cout << "RUN " << A[ i + 1 ] - A[ i ] - 2 << endl,
        cout << "JUMP " << A[ dp[ i ] ] - A[ i + 1 ] + 2 << endl;
    if( M - A[ N - 1 ] - 1 )
        cout << "RUN " << M - A[ N - 1 ] - 1 << endl;
}