【DP】【BFS】迷之阶梯
迷之阶梯
题目大意:
有n层阶梯,如果上面一层离这一层只有1个单位高度,就可以直接上去,也可以下去一层,当下去k层时,可以向上飞个单位高度,当然要找到一个小于等于这个高度的阶梯落脚,问到第n层的最少步数是多少
原题:
解题思路(非正解):
BFS枚举每一步,到了第n层就直接输出
代码:
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,dd,tt,bb,rr,a[205],p[205][205];
void bfs()
{
queue<int> d;//层数
queue<int> t;//向下走了几层
queue<long long>b;//步数
queue<long long>r;//可以向上多高
p[1][0]=1;
d.push(1);
t.push(0);
b.push(0);
r.push(1);
while (!d.empty())
{
dd=d.front();
d.pop();
tt=t.front();
t.pop();
bb=b.front();
b.pop();
rr=r.front();
r.pop();
for (int i=dd+1;i<=n;++i)
if (a[dd]+rr>=a[i])//可以到达
{
if (!p[i][0])//到达过就不要
{
d.push(i);
t.push(0);
b.push(bb+1);//步数加一
r.push(1);
p[i][0]=1;//记录退0步到达点i已经入队过了,记录下来,否则会死循环
if (i==n)//到了
{
printf("%lld",bb+1);//输出
return;//退出
}
}
}
else break;
if (dd>1&&(!p[dd-1][tt+1]))//可以向下
{
d.push(dd-1);//向下
t.push(tt+1);//加一
b.push(bb+1);//多了一步
r.push(rr*2);//可以跳的距离翻倍
p[dd-1][tt+1]=1;//记录
}
}
printf("-1");//到不了就输出-1
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i)
scanf("%lld",&a[i]);
bfs();
}
解题思路(正解):
DP,枚举当前层,从哪一层出发,向下多少层才跳,然后判断是否跳得到,跳的到就转移
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n;
long long a[205],f[205];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i)
scanf("%lld",&a[i]);
memset(f,0x7f,sizeof(f));
f[1]=0;
for (int i=2;i<=n;++i)//当前层
for (int j=i-1;j>0;--j)//从哪一层出发
for (long long t=1,k=0;k<j;++k,t*=2)//退多少层再跳,可以跳的距离相应地乘2
if (a[j-k]+t>=a[i])//判断是否跳得到
f[i]=min(f[i],f[j]+k+1);//往后退的步数还有跳也算一步
if (f[n]<f[0]) printf("%lld",f[n]);//f[0]没变过,所以是初始值,如果等于,就说明跳不到
else printf("-1");//不行就输出-1
}