题解 | #附加题#

动态规划题

递推公式比较重要

到达第i间房间 需要 偶数次 到达 第 i - 1次房

然后有传送门机制节省步数 所以需要 减去 dp[room[i - 1]] 的步数

最后得到 dp[i] = (dp[i - 1] + 1 + dp[i - 1] - dp[room[i - 1]] + 1) % maxStep

#include<iostream>
#include<vector>

using namespace std;
#define maxStep 1000000007 

int main() {
    int n;
    cin >> n;
    int *p = new int[n + 1];
    int *dp = new int[n + 1];
    
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    
    dp[1] = 0;
    
    for (int i = 2; i <= n + 1; i++) {
        dp[i] = (dp[i - 1] + 1 + dp[i - 1] + 1 - dp[p[i - 1]]) % maxStep;
    }
    
    cout << (dp[n + 1] < 0 ? dp[n + 1] + maxStep : dp[n + 1]);
    return 0;
}