描述

在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中L是桥的长度)。坐标为0的点表示桥的起点,坐标为L的点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数(包括S,T)。当青蛙跳到或跳过坐标为L的点时,就算青蛙已经跳出了独木桥。

题目给出独木桥的长度L,青蛙跳跃的距离范围S,T,桥上石子的位置。你的任务是确定青蛙要想过河,最少需要踩到的石子数。

输入格式

输入文件river.in的第一行有一个正整数L(1 <= L <=10^9),表示独木桥的长度。第二行有三个正整数S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数,其中1 <= S <= T <= 10,1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置(数据保证桥的起点和终点处没有石子)。所有相邻的整数之间用一个空格隔开。

输出格式

输出文件river.out只包括一个整数,表示青蛙过河最少需要踩到的石子数。

数据规模

对于30%的数据,L <= 10000;

对于全部的数据,L <= 10^9。

题解

一看题,这无后效性和最优子结构也太明显了,随手就可以列出转移方程。令dp[i]表示处于i位置时,最少还要踩到几个石子(包括当前点)才能到达对岸。bridge[i]为点i处的石子个数(0或1)。则

当0≤i<L时:dp[i] = min{dp[i+j]} + bridge[i] (S≤j≤T)

当i≥L时:dp[i]=0

问题的解即为dp[0]。

但是这样写完交上去最多只能得30分。直接硬搞,复杂度是O(L*(T-S))的,T-S最大为9,无关紧要,但是L的最大值则是令人发指的10^9(青蛙跳这么长距离不累死么 – -),不TLE……恐怕需要10年以后的CPU了。那怎么办呢?(思考过程也许比较繁琐,要结论请直接看倒数第5段)

数据范围往往是算法选择的最重要的提示。我们看到虽然L这么巨大,但是石子的总数却不超过100个。这说明什么?说明桥上必然有大段大段的无石子区间,而无石子区间的最大长度在极限情况下将接近10^9。即在跳跃中,青蛙经常会很郁闷地在巨长的无石子区间上跳啊跳啊,想踩个石子都踩不到。上面那个普通dp肯定会导致空白区间上大量的无必要决策而无谓耗费大量时间。要减少这种时间浪费,我们可以试图把大段的无石子区间等效转化为较短的无石子区间,从而使时间开销降至可承受范围。

首先考虑最简单的情况:S=T。这种情况下,这个诡异的青蛙只能跳固定的长度。而跳的起点是0位置,那么青蛙经过的就只有S(或者说T,一回事)的整数倍点。如果石子的位置为S的整数倍,那么青蛙就一定会踩到,否则一定踩不到。比如S=T=3,L=100,那么青蛙经过的点就为且仅为0,3,6,…,96,99。在21、27、33、66等处的石子就一定能踩到,而20、40、80、92等处的石子就踩不到。于是,当S=T时,我们只需要数位置为S整数倍的石子有几个就得到了答案,不需要进行上面说到的“等效转化”。

那如果S≠T呢?我们也从一个最简单的例子看起。假如S=5,T=6,青蛙从0位置开始跳,那么它可能到达的点是:

5,6,

10,11,12,

15,16,17,18,

20,21,22,23,24,

25,26,27,28,29,30,31,32,33,……

可以看到,这些点组成了一个个连续的区间,各相邻区间起点间的距离都是S=5,开始区间长度为2,然后长度变为3,4,然后完全连在一起,后面的位置都可达。如果桥上0~999都没有石子,1000处有一个石子,那么我们只关心青蛙是否选择跳到999,998,997,996,995,994这几个位置,因为青蛙在这段无石子区间上跳半天最后总会跳到这6个位置上,在无石子区间中不管怎么跳其实都无所谓。那么,我们完全可以无视25以后的数,把这段区间等效为0~25,以确保25以后所有位置都可达且有20~25这段连续区间来代替994~999这段等长的区间。这样,我们在这段无石子区间上的决策就大大减少了。

桥上的其他无石子区间是否可以如法炮制呢?答案是肯定的。对于以后任何一段长度大于25+6=31的无石子区间(这是采取“等效”措施的“门槛”),我们都可以把它的长度看成31。(25为什么要加上6呢?考虑一下,进入这段无石子区间后,青蛙开始往前跳的的起点,它可能不是区间本身的起点。)这样处理后,即使桥长度达到10^9,也可以在非常短的时间内出解。事实上,我们不仅可以把无石子区间长度等效为31,等效为36,121,500也都可以,只要长度比31大就行(当然“门槛”也要相应升高)。我们把这个等效区间的“最短”长度(本例中为31)称为“等效区间最短长度”。

下面推广。当S≠T时我们发现,在T不变的情况下,T-S越大(即S越小),等效区间最短长度越短。T-S不变的情况下,T越大,等效区间最短长度越长。那么对于题目给出的数据范围,S=9,T=10时(满足T-S最小且T最大)得到最大的“等效区间最短长度”为100。对于其他的S和T,我们不需要专门计算它们对应的等效区间最短长度,直接采用100这个值就可以了。

综上,若S=T,我们直接数位置能被S整除的石子个数;若S≠T,如果某无石子区间长度大于100,则等效为100,否则不变,然后再dp。

至于为什么有同学取比100小的数也AC了,我觉得(不一定对哈,没验证)应该是数据弱了。经实验,即使取20也可以AC,取10也才WA一个点。

对于等效区间最短长度的这番计算其实完全不必要。比赛时最好的方法是:取时间复杂度可接受的最大值……这样最省事。

上面可能做麻烦了,欢迎提供简明解法,谢谢。

最后说点题外话。这题我调了一晚上,郁闷死了。最后发现问题竟然是:石子位置没有按照升序排列,我却想当然这么处理了,结果一个点都过不去……

代码如下:

#include <iostream>
#include <fstream>
#include <bitset>
#include <cstdlib>
using namespace std;
unsigned long L_orig,L,S,T,M,pos[102],dp[12000],ans;
bitset<12000> bridge,flag;
long memo(long i){
    if(i>=L)    return 0;
    if(flag[i]) return dp[i];
    flag[i]=1,dp[i]=INT_MAX;
    for(int j=S;j<=T;j++)
        if(dp[i]>memo(i+j))
            dp[i]=memo(i+j);
    dp[i]+=bridge[i];
    return dp[i];
}
inline int cmp(const void *a,const void *b){
    return *(long*)a-*(long*)b;
}
int main(){
    ifstream cin("river.in");
    cin >> L_orig >> S >> T >> M;
    if(S==T)
        for(int i=1,tmp;i<=M;i++){
            cin >> tmp;
            if(tmp%S==0)    ans++;
        }
    else{
        pos[M+1]=L_orig;
        for(int i=1,counter=0;i<=M;i++) cin >> pos[i];
        qsort(pos,M+2, sizeof(pos[0]),cmp);
        for(int i=1;i<=M+1;i++){
            if(pos[i]-pos[i-1]-1<=100)  L+=pos[i]-pos[i-1];
            else    L+=100;
            bridge[L]=1;
        }
        ans=memo(0);
    }
    ofstream fout("river.out");
    fout << ans << endl;
    return 0;
}