笔试刷题-头条2018-07-08

题目描述：

/**
存在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:
4
例子说明1:
开始从房间1 只访问一次所以只能跳到p1即 房间1， 之后采用策略A跳到房间2，房间2这时访问了一次因此采用策略B跳到房间2，之后采用策略A跳到房间3，因此到达房间3需要 4 步操作。
*/

思路如下：

设dp[i]为到达i门，并且进入次数为偶数时需要移动的次数 一开始为0 第二次进入1要两次
由于题目要求dp[N]-1+1(减1是因为要求初始状态为进入1奇次，加1 偶N->奇N+1)

代码如下：

#include<stdio.h>
#include<iostream>
 
#define MAX_N 1005
#define MOD 1000000007
 
using namespace std;
 
int dp[MAX_N], pos[MAX_N];
 
int main()
{
    int N;
    while(cin>>N)
    {
        for(int n=1; n<=N; n++)
        {
            scanf("%d", pos+n);
        }
        if (N == 1)
        {
            cout << "1" << endl;
            continue;
        }
        for(int i=1; i<=N; i++)
        {
//            dp[i] = (dp[i-1]+1)%MOD;//第一次从i->i+1
//            dp[i] = (dp[i]+1)%MOD;//从i->pos[i]
//            dp[i] = (dp[i]+((dp[i-1]-(dp[pos[i]-1]+1)+MOD)%MOD))%MOD;//第一次到pos[i]->第二次i-1所需要步骤
//            dp[i] = (dp[i]+1)%MOD;//从第二次i-1->第二次i
                //合并
                dp[i] = (2 * dp[i - 1] %MOD- dp[pos[i] - 1] + 2) % MOD;
        }
        cout<<dp[N]<<endl;
    }
    return 0;
}