题解 P1052 【过河】

貌似某神犇把几篇题解都hack了~~（惶恐）~~。 本蒟蒻来发篇题解供大家参考（写的不好的地方请谅解）。 基本的思路很简单： 第一眼看这题的同学应该首先立即就会想到动规吧。~~（显而易见）~~ 因为它满足无后效性。 当前的每一个状态都可以由之前的状态转移过来。 当前的决策对之后都不会产生影响。 $\color{blue}But$动态规划最重要的就是状态转移方程。 恩，经过一段思考我们不难得出以下几条结论： 1. 当前的点$i$只与它前$i-j$个点有关($s\leq j\leq t$) 2. 如果当前的点是石头那么就是所有到达该点的位置所需踩的最少石头数加$1$ 经过上述的分析我们就可以得出我们的状态转移方程了： - 该点为石头： $dp[i] = min(dp[i],dp[i-j] +1)(s\leq j\leq t)$ - 该点不为石头： $dp[i] = min(dp[i],dp[i-j])(s\leq j\leq t)$ 分析到这好像差不多了。 等等！ 当我们猛然看到数据范围时就会发现这题没有这么简单： $L\leq 10^9$ 这么大的数据范围用数组存肯定存不下。 但是我们却惊奇发现石头数很小。 怎么办呢？先让我们来看看这张图：  其中$[S_i,T_i]$就是青蛙可以到的区间。 可以发现当$\color{Red}\textbf{s < t}$时， $s$和$t$一定会重合（当距离为$lcm(s,t)$即$s$，$t$的最小公倍数时） 而这以后的每个点都可以到达， 所以我们只需将每两个石头超过 $s\times t$ 的距离缩成$s \times t$就可以了当然如果你有疑虑的话也可以开大一点。 当$s = t$时我们只需枚举每个石头的坐标是否为$s$的倍数即可。 ```cpp #include<bits/stdc++.h> using namespace std; const int maxn = 150; const int maxl = 300 * 105; //其实开90 * 105就可以了； int L,s,t,m,stone[maxn],a[maxn],dp[maxl],base; //stone就是石头的初始位置；a为我们将石头初始化后的石头位置； bool vis[maxl]; //标记一下坐标上的该点是否为石头； int main() { ios::sync_with_stdio(0); // 关掉同步，加快cin的速度 cin >> L; cin >> s >> t >> m; base = s * t; for(int i = 1 ; i <= m ; ++ i) cin >> stone[i]; sort(stone + 1,stone + 1 + m); // 判段s == t的情况 if(s == t){ int cnt =0; for(int i = 1 ; i <= m ; ++ i) if(stone[i] % s == 0)cnt++; cout << cnt << endl; return 0; } for(int i = 1 ; i <= m ; ++ i) { // 离散化过程 int d = stone[i] - stone[i - 1]; if(d >= base)d = base; a[i] = a[i - 1] + d; vis[a[i]] = 1; } L = a[m] + base; // 将L变成最后一个石头的位置+s*t // 如果L - a[m] >= s * t就缩成s * t // 如果L - a[m] <= s * t就加上一个数使得它等于这个距离因为青蛙可能跳出独木桥 memset(dp,0x7f,sizeof(dp)); dp[0] = 0; // 初始化到原点寻最少踩0个石头 for(int i = 1 ; i <= L ; ++ i) for(int j = s ; j <= t ; ++ j) { if(i - j >= 0) { if(vis[i])dp[i] = min(dp[i - j] + 1,dp[i]); else dp[i] = min(dp[i - j],dp[i]); } } int ans = maxn; // 给答案赋一个较大的初值 for(int i = a[m] ; i <= L ; ++ i) ans = min(ans,dp[i]); cout << ans << endl; return 0; } ```