题解：P11827 [TOIP2024] 大步小步向前走
CX_xiaoli
·
·
题解
本题解把本人的思路和看题解以后的思路整理到了一起，希望对你有帮助。
我怎么不知道还有 TOIP。
题目大意
- 有 k 种步法，每种可以向前走 s_i 个坐标，现在要从坐标 0 走到 e，并且不能经过 n 个坐标，分别为 a_1,a_2,\dots,a_n。
- 要求不是总步数最小，而是大的步子走得尽可能多。
-
人家台湾的题就比我们细节多了，读题千万不能大意啊！
DP 分析
显然，令 dp_i 为从 0 走到 i 的最小步数……不对！我们要保证跨度大的步法被使用的次数最多，所以不能这么定义。那么状态是什么呢？既然一时想不出来，就先看看题目允许我们用怎样的时间复杂度来实现。注意到（本人止步于此）：
k\times(e-n)\le3\times10^5
既然数据范围实际这么小，空间如此宽裕，我们不妨力大砖飞地**定义 $dp_{i,x}$ 为走到坐标 $i$ 时步法 $j$ 的使用次数**。考虑到对于一整个数组的操作比较繁琐，这里不妨使用 $n$ 个 vector 作为 $dp$ 数组。而我们知道 vector 有内置的大小比较运算符，直接按位按字典序进行比较，所以 DP 的过程已经初具雏形：遍历有意义的坐标 $i$，遍历按跨度从大到小排序后的步法 $x$，如果转移源 $j=i-s_x$ 被成功转移过（确保状态合法），那么新开一个 vector $tmp=dp_j$，接着记录当前一步的贡献 $tmp_x=tmp_x+1$。接下来，如果原先的 $dp_i<tmp$（直接用 STL 的运算符），那么就更新 $dp_i=tmp$。大功告成！
# 输出答案
现在我们只是知道要走到坐标 $e$，每个步法的**满足条件**（大的步子走得尽可能多）的使用次数。那么怎么从中获取答案呢？难道暴力搜索，看怎样的一种步法使用顺序合法吗？肯定不可行。如果你了解过输出图的最短路的题，那你就会知道处理的方法：在 $dp_i$ 被 $dp_j$ 更新的时候记录 $pre_i=j$，DP 完后从 $pre_e$ 开始一路倒推到 $0$ 就能得到路径。正确性显然，因为 DP 无后效性，所以 $dp_i$ 中的最优解一定是最终 $dp_e$ 的最优解的一部分。而倒推出来的结果数组的长度就是使用的步法数量。
时间复杂度 $O(k\times(e-n)^2)$，但是这个 vector 大小比较基本跑不满，所以可以顺利通过。
# 细节与代码实现
- 使用的 vector 才初始化长度，不然 $3\times10^5$ 个 vector 全都初始化长度为 $3\times10^5$，肯定 [MLE](https://www.luogu.com.cn/record/291534551)。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+5, inf = 0x3f3f3f3f;
int n, k, e, a[N];
bool d[N], vis[N];
vector<int> cnt[N]; // 走到i坐标满足要求的走法
int pre[N], ans[N], idd; // 从哪里来的
signed main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k >> e;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
d[x] = true;
}
for (int i = 1; i <= k; i++) {
cin >> a[i];
}
sort(a + 1, a + k + 1, greater<int>());
cnt[0].resize(k + 1);
vis[0] = true;
for (int i = 1; i <= e; i++) {
if (!d[i]) {
cnt[i].resize(k + 1);
for (int x = 1; x <= k; x++) {
int j = i - a[x];
if (j >= 0 && !d[j] && vis[j]) {
vis[i] = true;
vector<int> tmp = cnt[j];
tmp[x]++;
if (cnt[i] < tmp) {
cnt[i] = tmp;
pre[i] = j;
}
}
}
}
}
if (!vis[e]) {
cout << -1;
} else {
int now = e;
while (now > 0) {
ans[++idd] = now;
now = pre[now];
}
cout << idd << '\n';
for (int i = idd; i > 0; i--) {
cout << ans[i] << ' ';
}
}
return 0;
}
```
[AC 记录](https://www.luogu.com.cn/record/291536232)，完结撒花！若此题解有助于君，恳留一赞！