题目传送门: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; }
Comments 2 条评论
我的bfs呢
@嫩爹 bfs已经被时代抛弃了哥们儿