头条2018年编程附加题，房间移动问题

 

房间移动问题

存在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

输出

4

说明

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

思路：

(1) 每个房间的移动次数记为d[j]，甲要移动到j，需要从j-1移动，即 d[j]  = d[j-1] + 1,

(2) 此时d[j]第一次访问，甲跳转pi[j]，移动1次，此时pi[j]为奇数次访问，状态相当于d[pi[j]-1]  +1,，甲需要从pi[j]开始移动，最后移动到 j-1, 且d[j-1]也应该再次变为偶数次访问， 移动次数为d[j-1] - d[pi[j]-1]  - 1, 移动到 j-1后，再加1，d[j-1] - d[pi[j]-1] + 1,为甲重新移动到j房间，(2)***移动了d[j-1] - d[pi[j]-1] +1次

(3) (1) + (2) = 2*d[j-1] - d[pi[j]-1] +2

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long mod = 1000000007;
int n = in.nextInt();
long d[] = new long [n+1];
int pi[] = new int[n+1];
for(int i = 1; i < n+1;i++){
pi[i] = in.nextInt();
}
if(n==1){
System.out.println(1);
return;
}
for(int j = 1; j < n+1; j++){
d[j] = (2 * d[j-1]%mod - d[pi[j]-1] + 2) % mod;
}
System.out.println(d[n]);
}
}