题解：AT_abc146_f [ABC146F] Sugoroku

简述题意：

从 0 开始，用最少的次数移动到 n，每次最多移动到与当前位置的距离小于等于 m 的位置上。若无法移动输出 -1；如果能到达n，输出满足移动次数最少且步数字典序最小的移动方案。

考虑贪心：

想要字典序最小，就要每次移动距离尽可能小；然而想要移动次数最少，就要每次移动距离尽可能大，这显然与字典序小矛盾了。

考虑从 n 走到 0，此时仍需最小次数，即每次移动距离尽可能大，但和正向移动不同的是，我们现在希望得到字典序比较大的解，矛盾显然就化解了。

CODE：

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NUM = 1e5 + 10;
ll n, m, cnt, id, stp[NUM];
string S;
bool dfs(ll x) {
	if (x == 0) return true;
	ll p = x, i = 1;
	for (; i <= m && x - i >= 0; i++)//从 x 向前看 m 位，取最靠前的 0 的位置。 
		if (S[x - i] == '0') p = x - i;
	stp[++id] = x - p, cnt++;//stp 倒叙存储每步的位移 
	return p == x? false: dfs(p);//p == x 说明取不到新的位置，即不能到达 
}
int main() {
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	cin >> n >> m >> S;
	if (dfs(n)) for(ll i = cnt; i > 0; i--) cout << stp[i] << ' ';
	else cout << -1;
	return 0;
}

题解：AT_abc146_f [ABC146F] Sugoroku

文章操作

相关推荐

评论

题解：AT_abc146_f [ABC146F] Sugoroku