求助,dfs奇奇怪怪(划掉)优化导致8,9wa
查看原帖
求助,dfs奇奇怪怪(划掉)优化导致8,9wa
313967
ditffit楼主2020/9/5 20:38
#include<iostream>
using namespace std;
int n,a,b,ans=200315;
int k[220],z[220];
void dfs(int flo,int mun)
{
//万恶之源 
	if(mun>z[flo]) return;
	z[flo]=mun;
//思路:当同是这一层楼,如果 当前按钮次数>曾经搜过的按钮次数
//或者说 当前的值超过了曾经的最优解 
//就直接放弃 毕竟没有必要了 .
//剩下常规dfs 
	if(flo==b){
		ans=min(ans,mun);
		return ;
	}
	if(flo+k[flo]<=n){
		dfs(flo+k[flo],++mun);
	}
	if(flo-k[flo]>=1){
		dfs(flo-k[flo],++mun);
	}
}
int main()
{
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		cin>>k[i]; z[i]=200315;
	}
	dfs(a,0);
	if(ans==200315) cout<<-1;
	else cout<<ans;
	return 0;
}

这个想法有什么问题吗,只有80分,8,9点WA,求助

2020/9/5 20:38
加载中...