NOIP 2015 过河(缩点+DP)

古城微笑少年丶 2022-05-16 01:00 164阅读 0赞

题目描述

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，...，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。  
题目给出独木桥的长度L，青蛙跳跃的距离范围S、T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

输入

每组输入的第一行有一个正整数L（1<=L<=109），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1<=S<=T<=10，1<=M<=100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。  
  
  
数据规模：  
对于30%的数据，L<=10000；  
对于全部的数据，L<=1e9。

输出

每组输出只包括一个整数，表示青蛙过河最少需要踩到的石子数。

分析：这题的数据范围是1e9，很明显数组是存不下的，所以首先需要离散化，最方便的离散化方法就是缩点，这里用的是2520缩点，因为 lcm（1，2，3，4，5，6，7，8，9，10）= 2520，那么从一个点出发，无论青蛙的跳跃距离是多少，它都一定可以到达下标为2520处，所以当在2520处没有石头的时候，可以将当前点向后移2520或者将后面的点向前移2520。然后这题很明显是一道DP的题，设dp\[i\]为在i点出所踩的最少石子数，那么在这点前面的 \[i - s，i - t\]这个范围内的点很明显都可能改变 i 点的值，因此需要选择dp\[ i - s\] 到 dp\[ i - t\]这个范围里的最小值来转移，如果 i 这个位置有石头就再让 dp\[i\] + 1，没有石头就不加，所以在dp之前我们也需要处理出缩点之后哪些位置上有石头。还有一个需要注意的地方是，因为题上说越过L也算作过桥，所以DP的终点不是一个点，而是一个范围。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const int maxn = 1e6+7;
    const int maxm = 1e2+27;
    const int inf = 0x3f3f3f3f;
    const double pi=acos(-1.0);
    const double eps = 1e-8;
    int dp[maxn],vis[maxn],a[maxm],road[maxm];
    int L,S,T,M,ans;
    
    int read()
    {
        char ch=getchar();int ret=0,f=1;
        while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
        return f*ret;
    }
    
    void slove()
    {
        rfup(i,1,M)
            road[i]=(a[i]-a[i-1])%2520;//计算每两个石头之间的相对距离
        rfup(i,1,M){
           a[i]=a[i-1]+road[i];//根据相对距离计算出每个石头缩点后所在位置
           vis[a[i]]=1;//此处有石头
        }
        L=a[M];//终点的左边界
        fup(i,1,L+10){//DP的终点是一个范围,所以L后面的也需要转移
            dp[i]=M;
            rfup(j,S,T){
                if(i>=j) dp[i]=min(dp[i],dp[i-j]);
                dp[i]+=vis[i];
            }
        }
        ans=M;
        fup(i,L,L+10) ans=min(ans,dp[i]);
        printf("%d\n",ans);
        return;
    }
    
    int main()
    {
        L=read(),S=read(),T=read(),M=read();
        rfup(i,1,M) a[i]=read();
        sort(a+1,a+1+M);//读入的石头不一定是排好序的,所以先排个序
        if(S==T){//如果S==T,则不存在状态转移,只有一种跳法
            ans=0;
            rfup(i,1,M) ans+=!(a[i]%S);
            printf("%d\n",ans);
            return 0;
        }
        slove();
        return 0;
    }

下面再给出看到的另一个大神的缩点方法及其证明：

[https://www.luogu.org/blog/littlejuruo/solution-p1052][https_www.luogu.org_blog_littlejuruo_solution-p1052]

蒟蒻表示根本看不懂。。。所以这种方法用到的是90点缩，但是需要注意，对于 s=t这种特殊情况，这种方法是不成立的，应为这种情况下，每次走的步数是固定的，因此这种情况需要特殊处理。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const int maxn = 1e4+7;
    const int maxm = 1e2+27;
    const int inf = 0x3f3f3f3f;
    const double pi=acos(-1.0);
    const double eps = 1e-8;
    int dp[maxn],vis[maxn],a[maxm],road[maxm];
    int L,S,T,M,ans;
    
    int read()
    {
        char ch=getchar();int ret=0,f=1;
        while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
        return f*ret;
    }
    
    void slove()
    {
        rfup(i,1,M){
            road[i]=a[i]-a[i-1];
            if(road[i]>90) road[i]=90;
        }
        road[M+1]=min(L-a[M],100);
        L=0;
        rfup(i,1,M){
            L+=road[i];
            vis[L]=1;//此处有石头
        }
        L+=road[M+1];
        rfup(i,1,L+9){
            dp[i]=inf;
            rfup(j,S,T){
                if(i>=j) dp[i]=min(dp[i],dp[i-j]+vis[i]);
            }
        }
        ans=inf;
        rfup(i,L,L+9) ans=min(ans,dp[i]);
        printf("%d\n",ans);
        return;
    }
    
    int main()
    {
        L=read(),S=read(),T=read(),M=read();
        rfup(i,1,M) a[i]=read();
        sort(a+1,a+1+M);
        if(S==T){
            ans=0;
            rfup(i,1,M) ans+=!(a[i]%S);
            printf("%d\n",ans);
            return 0;
        }
        slove();
        return 0;
    }

[https_www.luogu.org_blog_littlejuruo_solution-p1052]: https://www.luogu.org/blog/littlejuruo/solution-p1052