代码源#1008. Nearest Opposite Parity（记忆化搜索）

题目传送门：Nearest Opposite Parity - Problem - Daimayuan Online Judge

每个点出发可以往左走也可以往右走，注意可能会形成环，所以拓扑是不行的，可以用记忆化搜索。

默认dp[i]为0，这是一个不可能出现的结果，我们记作为“没更新过”的状态，如果dp[i] = -1说明更新过且到不了，如果为正整数说明是能到达终点的最小步数，这里一定要将res设为引用类型，便于处理后续可能出现的环。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 9;
int a[maxn], dp[maxn], N;

int dfs(int i)
{
	if(dp[i])return dp[i];
	
	int &res = dp[i] = -1;//用引用类型，十分关键
	
	if(i - a[i] >= 1)
	{
		if(a[i - a[i]] % 2 != a[i] % 2)res = 1;
		else
		{
			int tmp = dfs(i - a[i]);	
			if(tmp != -1)res = tmp + 1;
		}
	}
	
	if(i + a[i] <= N)
	{
		if(a[i + a[i]] % 2 != a[i] % 2)res = 1;
		else 
		{
			int tmp = dfs(i + a[i]);
			if(tmp != -1 && (res == -1 || tmp + 1 < res))res = tmp + 1;
		}
	}
	return res;
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N;
	for(int i = 1;i <= N; ++ i)cin >> a[i];
	for(int i = 1;i <= N; ++ i)cout << dfs(i) << ' ';
	return 0;
}