ct5_2: 跳棋★★题目描述：水平方向上有n个格子，格子上写着1到n的数字中的一个，游戏规则是：走到某一格，上面的数字假如是s，则可以选择跳到第s个格子或者前进一格，问你最少要走多少步才能到达最后一格并且返回起点。如：3 5 3 2 6 5 ，你去的时候可以一步一步到终点(5步)，也可以一开始就跳到第三格，再一步一步到终点(4步)，或者先前进一步再跳到第5格再一步一步地走(3步)，最少是3步到达。然后要再返回的时候，最少步数的走法是，左移两步再跳到第二格再左移一步(4步)，共7步。注意，跳的时候只能向着你的目标方向跳，不能反向。 输入：多组测试数据，第一行是一个整数n(1<=n<=1e5)，第二行是n个整数，表示对应的格子上写着的数。当n输入为0的时候结束。 输出：输出最少所需要的到达终点再返回原点的总步数 样例输入：63 5 3 2 6 50 样例输出：7 难度：Easy 解题报告: ct5_2 跳棋 题目要求: 从1开始出发走到第n个格子,走到某一格，上面的数字假如是s，则可以选择跳到第s个格子 或者前进一格, 但是有个条件,只能先前跳,如果第s个格子里的数字小于s,那么就不能跳了 到达第n个格子后,再向回走,规则和来的时候一样,也是只能向前走或者向前跳,假如走到第s 格如果第s格里的数字比s大,就不可以跳了,只能朝这第1个格子的方向走或者跳.题目求这样 一来一回最少用多少步. 基本想法: 其实回去的时候所走的步数和来的时候的步数没什么关系,所以可以分开考虑,而且来和回的过程 实质是一样的,我们可以用相同的方法分别求出来和回的最少步数,然后相加就得到了答案. 核心问题: 我们只考虑从1走到n的最少步数,如果这个可以求出来,那么回来的步数用同样的方法也可以求出来. 问题是这个最小步数怎么求? 核心算法: 先说算法过程,然后证明其正确性. 1.开一个数组f , f[n]示从1到第n个格子的最少步数. 2.开始时,把数组的第1个元素初始化为0,因为从1到1是0步,然后其它是无穷大( 具体多少看个人习惯 ) 3.从第1个格子开始,逐个对格子操作: 假设到了第h个格子, 计算f[h + 1], 用这时的f[h] + 1和 这时的f[h + 1]比较,然后取小值赋给f[h + 1], 如果第h个格子上的数s大于h,那么用同样的方法 计算f[s]: 用这时的f[h] + 1和f[s]比较,取小值赋给f[s].这样挨个对格子操作,那么对第n - 1 个格子操作完了就可以停止了,这时f[n]就是从1到达n的最小步数. 算法证明: 操作到第h个格子时,f[h]一定是1到h的最小步数. 首先,对于第一个格子,这个结论肯定是成立的,因为我们初始化了f[1] = 0. 假设对于前h - 1个格子这个结论都成立,那么我来证明对于第h个格子也成立 对于1到h的路径里,一定存在一条最优的路径,假设在这条路径上,上一个格子是k, 那么很显然,1到h的最小步数一定是1到k的最小步数加上1; 否则我们可以按照最 优路径从1走到k从而获得一条比1到k的最小步数更小的路径,但是这是不可能的. 由于题目要求只能向前走,所以k一定小于h,根据假设f(k)就是1到k的最小步数,而 到达h之前,我们在第k个格子操作时,已经计算了f(h),所以f(h)现在一定是最小步数. 证明完毕. 参考标程( 燕子的 ):#define PB_ID ct5_2#include <stdio.h>const int MAX_LENGTH = 100001;int main(void){ int nList[MAX_LENGTH]; int n; while(scanf("%d", &n),n) { int nCount[MAX_LENGTH]; for(int n1=1; n1<=n; ++n1) // Input & init { scanf("%d", nList+n1); nCount[n1]=MAX_LENGTH; } nCount[1]=0; for(int n1=1; n1<n; ++n1) // DP to end { if(nCount[n1+1] > nCount[n1] + 1) { nCount[n1+1] = nCount[n1] + 1; } if(nList[n1] > n1 && nCount[nList[n1]] > nCount[n1] + 1) { nCount[nList[n1]] = nCount[n1] + 1; } } for(int n1=1; n1<n; ++n1) // reset { nCount[n1]=MAX_LENGTH; } for(int n1=n; n1>1; --n1) // DP to beg { if(nCount[n1-1] > nCount[n1] + 1) { nCount[n1-1] = nCount[n1] + 1; } if(nList[n1] < n1 && nCount[nList[n1]] > nCount[n1] + 1) { nCount[nList[n1]] = nCount[n1] + 1; } } printf("%d\n", nCount[1]); // output } return 0;}
评论