警示后人()1-6用深搜TLE可能的解决方法
查看原帖
警示后人()1-6用深搜TLE可能的解决方法
994738
cannedH楼主2024/4/7 03:44

AC代码:

#include<iostream>
using namespace std;
int n, a, b,m;
int k[205], l[205];
void dfs(int i) {
	l[i] = m;
	int t1 = i - k[i]; int t2 = i + k[i];
	m++;
	if (t1 > 0 &&m<l[t1]) {  dfs(t1);  m--; }
	if (t2 <= n&&m<l[t2]) {  dfs(t2);  m--; }
}
int main() {
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++) { cin >> k[i]; }
	for (int i = 0; i < 205; i++) {
		l[i] = 500;
	}
	l[a] = 0;
	dfs(a);
	if (l[b] == 500) { cout << -1; return 0; }
	cout << l[b];
	return 0;
}

一些数字细节不用在意() 在我之前的1-6TLE代码中,bfs代码是这样的:

void dfs(int i) {
	if (l[i] < m ||m > l[b]) { return; }
	else { l[i] = m; }
	int t1 = i - k[i]; int t2 = i + k[i];
	if (t1 > 0 ) { m++;  dfs(t1);  m--; }
	if (t2 <= n) { m++;  dfs(t2);  m--; }
}

可以看出,问题在于递归调用数量,再进入一层dfs后判断是否需要减枝返回不如就在判断是否进入下一层时对当前层数做判断,也就是减少递归。引用讨论版中其他大佬的回答就是递归树太大,回不去了。 以上是蒟蒻的一点个人理解,如有问题欢迎大佬指出!

2024/4/7 03:44
加载中...