题解 P1052 【过河】

· · 题解

upd on 2020/11/15 ：修改了做法，现在可以通过hack数据

upd on 2020/07/25 : 修了一下 \LaTeX

说在前面：

为了让大家有更好的理解，我会尽量说的清晰，简洁一些。

读题（只看思路请跳过这一段）

简化一下本题的题意：

在一个数轴上有 M 个点。

你一次的移动距离可以是 S 到 T 区间中任意一个数，求从起点到终点最少碰到的点的个数。

思路：

很明显的，这是一道 DP 的例题。

从以下两个角度出发：

我们不难想到：

我们当前的点可以从前 S 到 T 个点到达。

到达时有两种情况，踩到石子或者没踩到石子。

不妨设 f[i] 表示在第 i 个点时踩到的最少的石子数。

如果没踩到石子：f[i]=min(f[i],f[i-j])

踩到了话: f[i]=min(f[i],f[i-j])+1

思路理清楚了么？

这里给出代码：

    for(register int i=1;i<=L+t;i++){
        for(register int j=s;j<=t;j++){
            if(i-j>=0){
                f[i]=min(f[i],f[i-j]);  
            }
            f[i]+=rock[i];
        }
    }

优化：

在一番深思熟虑之后，我想到了这道题的一些特殊情况。

如果数据给出来的石子间距不大，那还好。

如果像这样的话呢？（绿色小星星代表石子）：

一个石子和一个石子中间隔得非常开(1\times 10^8之类的数据)，你还会傻傻的暴力全跑一遍？

（不 T 飞就有鬼咯！）

所以，我们自然而然的想到了压缩路径。

如果有两个石子的间距很长，那我们拿区间 [S,T] 所有数的最小公倍数对它取余来得到新的间距，也不会对结果有什么影响。

为啥？这不是明摆着么？

你既然可以跳 [S,T] 区间里任意一个数，那你把这个区间对 lcm(S...T) 取余。

压缩掉的那部分又没有石子，你肯定可以到达其中任意一个点，那压缩掉这部分对结果肯定没有影响啊。

在我写代码的时候，为了写着更舒服（不用每次都求一遍最小公倍数），我用了 2520 来作为模数。

因为 lcm(1,2,3,4,...,10) = 2520 。

也就是可以得到这样的一段代码：

    for(register int i=1;i<=m;i++){
        re[i]=(a[i]-a[i-1])%2520; 
    }

但是 test#1 是一组hack数据，会让我的这个做法wa掉。

解决方法其实也很简单，我们在代码里加上这一行：

    if((a[i]-a[i-1])>=2520&&re[i]<=t){
        re[i]+=2520;
    }

就可以了。

解释一下为什么。

如果我们先处理出来的那个 a[i]-a[i-1] 是大于 2520 的，那么模完就有可能会出现这个新的 re[i] 小于 t 的情况。

那么意味着什么呢？

两块石子可能会重合在一起。

那您就挂了啊。

所以出现这种情况的时候再给 re[i] 加上 2520 就可以了。

code：

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

int a[104];
int re[104];
int rock[1000005];
int f[1000005]; 
int L,s,t,m;

int main(){
    cin>>L;
    cin>>s>>t>>m;
    for(register int i=1;i<=m;i++){
        cin>>a[i];
    } 
    sort(a+1,a+m+1); 
    for(register int i=1;i<=m;i++){
        re[i]=(a[i]-a[i-1])%2520; 
        if((a[i]-a[i-1])>=2520&&re[i]<=t){
            re[i]+=2520;
        }
    }
    for(register int i=1;i<=m;i++){
        a[i]=a[i-1]+re[i];
        rock[a[i]]=1; 
    }
    L=a[m];
    for(register int i=0;i<=L+t;i++){
        f[i]=m;
    } 
    f[0]=0;
    for(register int i=1;i<=L+t;i++){
        for(register int j=s;j<=t;j++){
            if(i-j>=0){
                f[i]=min(f[i],f[i-j]);  
            }
            f[i]+=rock[i];
        }
    }

    int res=m;

    for(register int i=L;i<L+t;i++){
        res=min(res,f[i]);
    }
    cout<<res<<endl;
    return 0;
}

谨以此题解纪念我AC的第一道蓝题。