ZJ1 附加题

思路：暴力模拟超时！动态规划通过！dp[i]表示第一次到达i需要移动次数！1<=pi<=i即策略B只会倒退，如果使用策略A前进到达i房间只会到达i-1房间偶数次+1！那么递推公式为dp[i]=(dp[i-1]+1+dp[i-1]-dp[arr[i-2]]+1)% MOD！即第一次到达dp[i-1]移动一次到arr[i-2]再从arr[i-2]到i-1再移动一步到i！同时注意由于存在减法故可能会出现负数！那么最后还需要根据dp[n+1]正负(dp[n+1]<0)?dp[n+1]+MOD:dp[n+1]！

// 暴力模拟 超时
const rl = require("readline").createInterface({ input: process.stdin })
var iter = rl[Symbol.asyncIterator]()
const readline = async () => (await iter.next()).value
void async function () {
    // 取模
    let MOD=1e9+7
    // 获取房间数
    let n = parseInt((await readline()).trim())
    // 获取策略
    let arr = (await readline()).trim().split(/\s+/).map(Number)
    // dp数组
    let dp=Array(n+1).fill(0)
    // dp[1] 初始化为1
    let i = 1
    // 记录次数
    let res = 0
    while(i!==(n+1))
    {
        // 访问次数加一
        dp[i]++
        res++
        // 根据奇偶性判断
        if(dp[i]%2==0)
            i++
        else
            i=arr[i]
    }
    console.log(res%MOD)
}()

// 动态规划 通过
const rl = require("readline").createInterface({ input: process.stdin })
var iter = rl[Symbol.asyncIterator]()
const readline = async () => (await iter.next()).value
void async function () {
    // 取模
    let MOD=1e9+7
    // 获取房间数
    let n = parseInt((await readline()).trim())
    // 获取策略 注意arr有效数据从0开始 dp有效数据从1开始
    let arr = (await readline()).trim().split(/\s+/).map(Number)
    // dp数组 dp[i]表示第一次到达i需要移动次数
    let dp=Array(n+2).fill(0)
    // 1<=pi<=i 只会倒退 前进到达i房间只会到达i-1房间偶数次+1
    for(let i=2;i<=n+1;i++)
    {
        // 第一次到达dp[i-1]移动一次到arr[i-2]再从arr[i-2]到i-1再一步i
        dp[i]=(dp[i-1]+1+dp[i-1]-dp[arr[i-2]]+1)%MOD
    }
    console.log((dp[n+1]<0)?dp[n+1]+MOD:dp[n+1])
}()