牛客周赛54：D.清楚姐姐跳格子（bfs）

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述

          \,\,\,\,\,\,\,\,\,\,老妪遂递一羊皮卷轴，上面什么都没有，清楚欲问，老妪却缄口不言。
          \,\,\,\,\,\,\,\,\,\,清楚性格刚直，放下鼠资，正欲再问，忽觉眼前一花，老妪和店铺却都消失不见，唯卷轴与竹鼠。
          \,\,\,\,\,\,\,\,\,\,“怪哉”，清楚回头走，见到地上有一些格子。

          \,\,\,\,\,\,\,\,\,\,清楚正在玩跳格子游戏。地上有 nnn 个格子，清楚一开始在 111 号格子，目标是 nnn 号格子。

          \,\,\,\,\,\,\,\,\,\,第 iii 个格子上有一个数字 aia_iai​ ，清楚在这个格子上可以往左右两边选一个方向，然后选择 aia_iai​ 的一个正整数因子作为长度，进行一次跳跃，但是不可以跳出边界。
          \,\,\,\,\,\,\,\,\,\,请问清楚最少跳多少步，就可以到达 nnn 号格子。

输入描述:

          \,\,\,\,\,\,\,\,\,\,第一行输入一个整数 n ( 1≤n≤103 )n\ (\ 1 \leq n \leq 10^3\ )n ( 1≤n≤103 ) 代表格子数量。\,\,\,\,\,\,\,\,\,\,第二行输入 nnn 个整数 a1,a2,…,an ( 1≤ai≤1018 )a_1,a_2,\dots,a_n\ (\ 1 \leq a_i \leq 10^{18}\ )a1​,a2​,…,an​ ( 1≤ai​≤1018 ) 代表格子上的数字。

输出描述:

          \,\,\,\,\,\,\,\,\,\,在一行上输出一个整数，代表到达终点需要的最少步数 。

示例1

输入

复制5 2 3 1 5 4

5
2 3 1 5 4

输出

复制2

2

说明

          \,\,\,\,\,\,\,\,\,\,在 111 号节点 ，选择 a1a_1a1​ 的因子 111 ，往右跳 111 步，到达 222 号节点。\,\,\,\,\,\,\,\,\,\,在 222 号节点 ，选择 a2a_2a2​ 的因子 333 ，往右跳 333 步，到达 555 号节点。

做法

直接bfs搜就好了

#include<bits/stdc++.h>
using namespace std;
int vis[1010];
long long a[1010];
int n;
struct ty{int x,cnt;
};
queue<ty> q;
void bfs(){q.push({1,0});while(!q.empty()){ty tmp=q.front();q.pop();if(tmp.x==n){cout<<tmp.cnt;return ;}if(vis[tmp.x]) continue;vis[tmp.x]=1;for(int i=1;i<=n;i++){if(a[tmp.x]%i) continue;if(i+tmp.x<=n&&vis[tmp.x+i]==0){q.push({tmp.x+i,tmp.cnt+1});}if(tmp.x-i>=1&&vis[tmp.x-i]==0){q.push({tmp.x-i,tmp.cnt+1});}}}
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);bfs();
}

wa的原因

因为这几天写了洛谷的跳跃机器人那题，而且最近一直在学dp，就只想着用dp了。不过这题好像不能用dp写。这个后效性好像解决不了，还是说之前的dp写法就是假的？？？