题解 | #附加题#

动态规划解题思路

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

递推公式如下：
memo[i]=memo[i-1]+2+f(p[i-1])
这里p[i-1]指的是房间号为i的房间里传送门去的房间,
+2是因为在进入房间之后，由于第一次，需要进入一次传送门，在进入下个房间时还需要一次移动

f(p[i-1])=memo[i-1]-memo[p[i-1]-1]
这个公式是因为在进入传送门后，由于房间访问次数为偶数（实际上访问过的房间访问次数均为偶数），需要按照之前的流程再走一遍

python代码如下

def visit(n,p):
    memo=[0]*(n+1)
    memo[1]=2
    for i in range(2,n+1):
        memo[i]=memo[i-1]+2
        if p[i-1]!=i:
            memo[i]+=memo[i-1]-memo[p[i-1]-1]
        memo[i]=memo[i]%1000000007                    
    return memo[n]

n=int(input())
p=list(map(int,input().split()))
print(visit(n,p))