- 影分身过河
XJOI - 题目ID：15694必做题100分
最新提交：
Time Limit Exceeded
60 分
历史最高：
Time Limit Exceeded
60 分
时间限制: 1000ms
空间限制: 262144kB
题目描述
题目描述
小兰进入森林探险后迷路了，现在有一条河挡在了他的面前，好在河上漂浮着
𝑛
n个木桩，每个木桩都有自己的编号(
1
,
2
,
.
.
.
𝑛
1,2,…n)以及魔法值
𝑎
𝑖
a
i
(可能是正数也可能是负数)，小兰是忍者高手，当他站在第
𝑖
i个木桩上时，如果该木桩的魔法值
𝑎
𝑖
0
a
i
0，那么他可以使用影分身之术选择传送到第
𝑖
𝑘
(
1
≤
𝑘
≤
𝑎
𝑖
)
i+k(1≤k≤a
i
)个木桩上，如果木桩的魔法值
𝑎
𝑖
<
0
a
i
<=0，那么他可以传送到
[
1
,
𝑖
+
𝑎
𝑖
]
[1,i+a
i
]中的任意一个木桩上。
现在小兰在
1
1号木桩，他需要传送到编号为
𝑛
n的木桩上才能顺利过河，每次使用影分身之术都会消耗
1
1点体力，小兰想尽可能的节省体力，他想知道最少消耗多少体力才能顺利过河，如果无论如何都无法过河，则输出
−
1
−1。
输入描述
第一行包含一个正整数
𝑛
(
2
≤
𝑛
≤
2000
)
n(2≤n≤2000)。
第二行包含
𝑛
n个整数
𝑎
1
,
𝑎
2
,
.
.
.
,
𝑎
𝑛
(
1
≤
∣
𝑎
𝑖
∣
≤
2000
)
a
1
,a
2
,…,a
n
(1≤∣a
i
∣≤2000)，表示木桩的魔法值。
输出描述
如果能够过河，输出一个整数，表示最少消耗的体力；
否则输出
−
1
−1。
样例1
输入样例
4
2 2 -1 2
输出样例
2
样例2
输入样例
2
-1 -2
输出样例
-1
样例说明
对于样例1，小兰在
1
1号木桩上可以选择传送到
2
2号木桩，再从
2
2号木桩传送到
4
4号木桩从而顺利过河。
一共传送
2
2次，消耗的体力为
2
2。
对于样例2，小兰只能一直呆在
1
1号木桩上。
深搜代码：
#include<iostream>
using namespace std;
int n,a[2005];
bool f;
int minn=1e9;
void dfs(int x,int num){
if(x==n){
f=1;
minn=min(minn,num);
return ;
}
for(int i=x+1;i<=x+a[x]&&i<=n;i++){
if(num+1>minn){
return ;
}
dfs(i,num+1);
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
dfs(1,0);
if(f) cout<<minn;
else cout<<"-1";
return 0;
}
广搜代码：
#include<iostream>
#include<queue>
using namespace std;
struct node{
long long x,step;
};
int main(){
long long n,a[200005];
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
queue<node>q;
q.push(node{1,0});
while(!q.empty()){
node now=q.front();
long long x=now.x,s=now.step;
q.pop();
for(int i=x+1;i<=a[x]+x;i++){
q.push(node{i,s+1});
if(i==n){
cout<<s+1;
return 0;
}
}
}
cout<<"-1";
return 0;
}
