这题不要再用DFS了!
查看原帖
这题不要再用DFS了!
767561
Ascnbeta楼主2024/7/7 10:53

如果dfs不加 visvis 会MLE,加上会有TLE+MLE,再加上如果超过当前答案就 return 的优化也会造成前 66 个测试点TLE

附我的DFS代码,佬们可以看看还能怎么优化:

#include <bits/stdc++.h>
using namespace std;
int k[205],g[205],b,n,ans = 0x7ffffff,cnt1;
bool f[205];
void dfs(int c,int s,int cnt){
	//if (++cnt1 > 1e6) return;数据加强前为了过#1需要加上这个卡一下,现在加这个会前6点WA,可知前6点都需要递归1e6次+;
	if (cnt > ans) return;//最短优化
	if (c == b) {
		ans = min(ans,cnt);
		return;
	}
	f[c] = true;//相当于vis数组
	if (c - s > 0 && !f[c-s]) dfs(c - s,k[c-s],cnt + 1); 
	if (c + s <= n && !f[c+s]) dfs(c + s,k[c+s],cnt + 1);
	f[c] = false;
}
int main () {
	int a;
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++) cin >> k[i];
	f[a] = true;
	dfs(a,k[a],0);
	if (ans == 0x7ffffff) ans = -1; 
	cout << ans << endl;
	return 0;
}
2024/7/7 10:53
加载中...