[Leaf] [P1052] 过河

luogu-p1052-过河">Luogu-P1052 过河

1. 核心逻辑

• 问题本质: 在极长坐标轴上进行跳跃，求踩到石子的最小数量。

• 破局转换:

  1. 瓶颈分析: $L = 10^9$ 无法直接开数组，但石子数 $M \le 100$ 非常稀疏。

  2. 路径压缩: 当两个石子间距极远时，中间的大量空白路径对“可达性”的影响是周期性的。

  3. 安全阈值: 若距离 $diff > S \times T$ (或 $LCM(1 \dots 10) = 2520$)，则超出部分的距离是多余的。通常取 $LCM$ 作为步进压缩的基础，或者暴力设定一个足够大的阈值（如 $100$）。

  4. 转移: f[i] = min(f[i - j]) + is_stone[i] ($S \le j \le T$)。

2. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 50;
int l, s, t, m;
int a[105], stone[maxn], f[maxn];

int main( ) 
{
    cin >> l >> s >> t >> m;
    for( int i = 1; i <= m; ++ i ) cin >> a[i];

    // 特判 S == T: 只能固定跳跃
    if( s == t ) 
    {
        int cnt = 0;
        for( int i = 1; i <= m; ++ i ) if( a[i] % s == 0 ) ++ cnt;
        cout << cnt << "\n";
        return 0;
    }

    sort( a + 1, a + m + 1 );
    a[0] = 0;
    
    int current_len = 0;
    const int gap = 100; // 安全压缩阈值

    for( int i = 1; i <= m; ++ i ) 
    {
        int d = a[i] - a[i - 1];
        current_len += min( d, gap );
        stone[ current_len ] = 1;
    }
    
    // 终点也需要压缩
    l = current_len + min( l - a[ m ], gap );

    memset( f, 0x3f, sizeof( f ) );
    f[ 0 ] = 0;

    for( int i = 1; i <= l + t; ++ i ) 
    {
        for( int j = s; j <= t; ++ j ) 
        {
            if( i >= j ) f[i] = min( f[i], f[i - j] + stone[i] );
        }
    }

    int ans = 105;
    for( int i = l; i <= l + t; ++ i ) ans = min( ans, f[i] );
    cout << ans << "\n";

    return 0;
}

3. 归档备注

• 复杂度: $O(M \cdot \text{Gap} \cdot (T-S))$。

• 关键点: 区分坐标轴物理长度与逻辑状态的关系。由于可以跳过终点，最终答案需在 $[L, L+T]$ 范围内扫一遍。

• 关联知识点: 线性DP