ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 简单
  4. 正文

代码源#1008. Nearest Opposite Parity(记忆化搜索)

2022年10月17日 163点热度 0人点赞 2条评论

题目传送门: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ daimayuan dfs 思维 算法竞赛 记忆化搜索
最后更新:2022年10月17日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

  • 嫩爹

    我的bfs呢

    2022年10月17日
    回复
    • Eriktse

      @嫩爹 bfs已经被时代抛弃了哥们儿

      2022年10月18日
      回复
  • razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
    取消回复

    订阅本站
    Loading
    文章目录
    • 代码

    COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

    Theme Kratos Made By Seaton Jiang

    赣ICP备2022001555号-1

    赣公网安备 36092402000057号