P1052 过河网页链接P1052 过河题目描述在河上有一座独木桥一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点0 , 1 , ⋯ , L 0,1,\cdots,L0,1,⋯,L其中L LL是桥的长度。坐标为0 00的点表示桥的起点坐标为L LL的点表示桥的终点。青蛙从桥的起点开始不停的向终点方向跳跃。一次跳跃的距离是S SS到T TT之间的任意正整数包括S , T S,TS,T。当青蛙跳到或跳过坐标为L LL的点时就算青蛙已经跳出了独木桥。题目给出独木桥的长度L LL青蛙跳跃的距离范围S , T S,TS,T桥上石子的位置。你的任务是确定青蛙要想过河最少需要踩到的石子数。输入格式输入共三行第一行有1 11个正整数L LL表示独木桥的长度。第二行有3 33个正整数S , T , M S,T,MS,T,M分别表示青蛙一次跳跃的最小距离最大距离及桥上石子的个数。第三行有M MM个不同的正整数分别表示这M MM个石子在数轴上的位置数据保证桥的起点和终点处没有石子。所有相邻的整数之间用一个空格隔开。输出格式一个整数表示青蛙过河最少需要踩到的石子数。输入输出样例 #1输入 #110 2 3 5 2 3 5 6 7输出 #12说明/提示【数据范围】对于30 % 30\%30%的数据1 ≤ L ≤ 10 4 1\le L \le 10^41≤L≤104对于100 % 100\%100%的数据1 ≤ L ≤ 10 9 1\le L \le 10^91≤L≤1091 ≤ S ≤ T ≤ 10 1\le S\le T\le101≤S≤T≤101 ≤ M ≤ 100 1\le M\le1001≤M≤100。【题目来源】NOIP 2005 提高组第二题解题思路本题是路径压缩 动态规划的经典问题。独木桥长度L LL可达10 9 10^9109无法直接开数组进行 DP但跳跃距离S , T S,TS,T很小1 ≤ S ≤ T ≤ 10 1 \le S \le T \le 101≤S≤T≤10且石子数量M ≤ 100 M \le 100M≤100。利用“当两个石子间距离超过某个阈值时中间的空隙对最优解没有影响”这一性质可以将桥的长度压缩到可接受的范围再在新路径上做线性 DP 求最少踩到的石子数。1. 问题等价转化青蛙从位置0 00出发每次可跳S ∼ T S \sim TS∼T步目标是跳到≥ L \ge L≥L的位置过程中尽量少踩石子。若S T S TST每次跳跃距离固定为S SS那么只有位置能被S SS整除的石子才会被踩到。直接统计满足x % S 0的石子数即可。若S T S TST则存在多种跳跃选择。由于T ≤ 10 T \le 10T≤10两个石子之间的距离如果超过某个阈值代码中取90 9090中间这段没有石子的长距离对状态转移的影响可以等价缩短为90 9090因为青蛙可以通过多次小跳跨过这段空白不会改变相对最优决策。2. 算法实现特殊情况处理若S T S TST读入所有石子位置统计能被S SS整除的石子个数并输出。一般情况读入石子位置数组b排序并在开头添加位置0 00作为起点。路径压缩计算相邻石子包括起点0 00和终点L LL之间的距离但每个距离最大取90 9090。用d[i]记录压缩后的距离L累加得到压缩后的总长度。用vis[pos]标记压缩后每个石子所在的新位置。动态规划设dp[i]表示到达压缩后位置i ii时最少踩到的石子数。初始化dp[0] 0其余为无穷大。对于i ii从1 11到L 9 L9L9枚举跳跃距离j ∈ [ S , T ] j \in [S, T]j∈[S,T]若i ≥ j i \ge ji≥j则d p [ i ] min ⁡ ( d p [ i ] , d p [ i − j ] v i s [ i ] ) dp[i] \min(dp[i], dp[i-j] vis[i])dp[i]min(dp[i],dp[i−j]vis[i])其中vis[i]表示压缩后位置i ii是否有石子1 11有0 00无。最终答案在i ∈ [ L , L 9 ] i \in [L, L9]i∈[L,L9]范围内取dp[i]的最小值因为青蛙可能跳过终点。输出答案。3. 复杂度分析时间复杂度压缩后路径长度约为M × 90 ≈ 9000 M \times 90 \approx 9000M×90≈9000DP 内层枚举T − S 1 ≤ 10 T-S1 \le 10T−S1≤10种跳跃总运算量约9 × 10 4 9 \times 10^49×104非常快。空间复杂度需要存储压缩后的标记数组和 DP 数组大小约10000 1000010000空间消耗极小。总结本题的核心在于利用小跳跃范围的特点进行路径压缩将10 9 10^9109的桥长缩减到10 4 10^4104以内从而可以用线性 DP 求解。压缩阈值取90 9090是保守且安全的因为T ≤ 10 T \le 10T≤10T × ( T − 1 ) T \times (T-1)T×(T−1)最大为90 9090。特殊处理S T STST避免不必要的 DP。整个算法高效且易于实现。代码简要说明全局数组dp存储最小踩石数vis标记压缩后位置是否有石子b存储原始石子位置。特殊处理if (S T)时直接统计整除石子数并返回。路径压缩排序石子在b[0]放置起点0 00。对每个间隔取min(b[i] - b[i-1], 90)作为新距离累加得到新长度L。在新位置L处标记石子vis[L] 1。终点后的距离也做类似处理保证可以跳过终点。DP 转移双重循环外层遍历位置内层遍历跳跃距离更新最小值。答案在[L, L9]范围内取dp最小值输出。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll dp[10005],d[10005],b[10005],vis[10005],L,S,T,n;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld,L);scanf(%lld%lld%lld,S,T,n);if(ST){ll c0,x;for(ll i1;in;i){scanf(%lld,x);c((x%S)0);}printf(%lld\n,c);return0;}for(ll i1;in;i)scanf(%lld,b[i]);sort(b1,bn1);b[0]0;dp[0]0;d[n1]min(L-b[n],100LL);L0;for(ll i1;in;i){d[i]min(b[i]-b[i-1],90LL);Ld[i];vis[L]1;}Ld[n1];for(ll i1;iL9;i){dp[i]INF-1;for(ll jS;jT;j)if(ij)dp[i]min(dp[i],dp[i-j]vis[i]);}ll ansINF-1;for(ll iL;iL9;i)ansmin(ans,dp[i]);printf(%lld,ans);return0;}