甘肃住房和城乡建设厅网站,网页qq邮箱登录,响应式模板,上海企业建设网站服务迷之阶梯
题目大意#xff1a;
有n层阶梯#xff0c;如果上面一层离这一层只有1个单位高度#xff0c;就可以直接上去#xff0c;也可以下去一层#xff0c;当下去k层时#xff0c;可以向上飞2k{2}^{k}2k个单位高度#xff0c;当然要找到一个小于等于这个高度的阶梯落…迷之阶梯
题目大意
有n层阶梯如果上面一层离这一层只有1个单位高度就可以直接上去也可以下去一层当下去k层时可以向上飞2k{2}^{k}2k个单位高度当然要找到一个小于等于这个高度的阶梯落脚问到第n层的最少步数是多少
原题 解题思路非正解
BFS枚举每一步到了第n层就直接输出
代码
#includequeue
#includecstdio
#includecstring
#includeiostream
using namespace std;
int n,dd,tt,bb,rr,a[205],p[205][205];
void bfs()
{queueint d;//层数queueint t;//向下走了几层queuelong longb;//步数queuelong longr;//可以向上多高p[1][0]1;d.push(1);t.push(0);b.push(0);r.push(1);while (!d.empty()){ddd.front();d.pop();ttt.front();t.pop();bbb.front();b.pop();rrr.front();r.pop();for (int idd1;in;i)if (a[dd]rra[i])//可以到达{if (!p[i][0])//到达过就不要{d.push(i);t.push(0);b.push(bb1);//步数加一r.push(1);p[i][0]1;//记录退0步到达点i已经入队过了记录下来否则会死循环if (in)//到了{printf(%lld,bb1);//输出return;//退出}}}else break;if (dd1(!p[dd-1][tt1]))//可以向下{d.push(dd-1);//向下t.push(tt1);//加一b.push(bb1);//多了一步r.push(rr*2);//可以跳的距离翻倍p[dd-1][tt1]1;//记录}}printf(-1);//到不了就输出-1
}
int main()
{scanf(%d,n);for (int i1;in;i)scanf(%lld,a[i]);bfs();
}解题思路正解
DP枚举当前层从哪一层出发向下多少层才跳然后判断是否跳得到跳的到就转移
代码
#includecstdio
#includecstring
#includeiostream
using namespace std;
int n;
long long a[205],f[205];
int main()
{scanf(%d,n);for (int i1;in;i)scanf(%lld,a[i]);memset(f,0x7f,sizeof(f));f[1]0;for (int i2;in;i)//当前层for (int ji-1;j0;--j)//从哪一层出发for (long long t1,k0;kj;k,t*2)//退多少层再跳,可以跳的距离相应地乘2if (a[j-k]ta[i])//判断是否跳得到f[i]min(f[i],f[j]k1);//往后退的步数还有跳也算一步if (f[n]f[0]) printf(%lld,f[n]);//f[0]没变过所以是初始值如果等于就说明跳不到else printf(-1);//不行就输出-1
}
