首页 > 试题广场 >

附加题

[编程题]附加题

热度指数：29675 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

存在n+1个房间，每个房间依次为房间1 2 3...i，每个房间都存在一个传送门，i房间的传送门可以把人传送到房间pi(1<=pi<=i),现在路人甲从房间1开始出发(当前房间1即第一次访问)，每次移动他有两种移动策略：
A. 如果访问过当前房间 i 偶数次，那么下一次移动到房间i+1；
B. 如果访问过当前房间 i 奇数次，那么移动到房间pi；
现在路人甲想知道移动到房间n+1一共需要多少次移动；

输入描述:

第一行包括一个数字n(30%数据1<=n<=100，100%数据 1<=n<=1000)，表示房间的数量，接下来一行存在n个数字 pi(1<=pi<=i), pi表示从房间i可以传送到房间pi。

输出描述:

输出一行数字，表示最终移动的次数，最终结果需要对1000000007 (10e9 + 7) 取模。

示例1

输入

2
1 2

输出

说明

开始从房间1 只访问一次所以只能跳到p1即 房间1， 之后采用策略A跳到房间2，房间2这时访问了一次因此采用策略B跳到房间2，之后采用策略A跳到房间3，因此到达房间3需要 4 步操作。

算法知识视频讲解

卡题魔法少年

发表于 2020-08-15 14:37:18

从题目中，我们发现1<=pi<=i，说明我们只会被传送到当前房间之前的房间（包括当前房间）。所以当我们到i房间时，我们已经走过所有从第一个房间到第i-1个房间且均为偶数次。我们定义dp[i]表示从第一个房间达到第i个房间且为偶数次的移动次数。状态转移方程为dp[i] = dp[i-1] 展开全文

Louie.Ye

发表于 2021-03-20 16:46:12

1. 题目意思[写博客为了记录一下这道题我很困扰] 1.老实说，题目意思我都没读懂。。。按照例子走,刚开始的1算访问次数，但不算移动次数的。对于移动的思路我是一点没理清楚。。还想多了会不会有pi到不了后面的情况。。肯定不会啊，题目都没说到不了输出情况测试数据肯定不会那么邪门。2. 观摩大佬的思路皮皮展开全文

牛客678001545号

发表于 2022-04-08 12:59:28

题目关键点：传送房间pi(1<=pi<=i)，也就是说明只能原地传送或者向前传送。于是可以得出：从房间i到达房间i+1时，房间i被访问了偶数次（即可认为被访问了0次）。同理可知，房间i+1之前的所有房间都可被视为没有被访问。令 to_room[i] 表示房间i传送到的房间，ste 展开全文

牛客386231296号

发表于 2021-08-10 16:06:22

动态规划解题思路由于pi<=i,所以要前往n+1个房间只能通过策略1：即访问n房间偶数次向前一步，因此前往n+1房间的问题就可以看成前往n房间，就可以用动规思路去求解memo[i]表示前往房间号为i+1的房间需要的次数，memo[0]=0,memo[1]=2 递推公式如下：memo[i]= 展开全文