题解 | #附加题#

题目关键点：传送房间pi(1<=pi<=i)，也就是说明只能原地传送或者向前传送。

于是可以得出：从房间i到达房间i+1时，房间i被访问了偶数次（即可认为被访问了0次）。同理可知，房间i+1之前的所有房间都可被视为没有被访问。

令 to_room[i] 表示房间i传送到的房间，step[i] 表示从1号房间开始到i所需要的操作次数，step[1]=0。

则：分析step[i+1]，到达房间i已经进行的操作为step[i]，然后额外操作1次，来到了房间to_room[i]，而从房间to_room[i]再回到房间i需要的操作次数为step[i]-step[to_room[i]]，此时再回到房间i时，i已经被访问两次，最后进行1次操作后就到达了房间i+1。
最终得出：step[i+1]=step[i]+1+step[i]-step[to_room[i]]+1;
即：step[i+1]=2*step[i]-step[to_room[i]]+2;

注意：

1. 由于数据范围的要求，所求得的step应该为正，所以step数组应该定义为unsigned int否则在计算过程中会超过int的范围导致结果错误。
2. 应该在step[i+1]原有的计算公式上再多加一个MAX_STEP（10e9+7），否则会出现 step[a]<step[b]（a>b） 的情况，显然是不合理的。

代码如下：

#include<iostream>
#define MAX_STEP 1000000007
using namespace std;
int main(){
    int n;
    cin>>n;
    unsigned int to_room[n+1],step[n+2];
    for(int i=1;i<=n;i++){
        cin>>to_room[i];
        step[i]=0;
    }
    for(int i=2;i<=n+1;i++){
        step[i]=(2*step[i-1]-step[to_room[i-1]]+2+MAX_STEP)%MAX_STEP;
    }
    cout<<step[n+1]<<endl;
    return 0;
}