题解 | 附加题

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    static const long long MOD = 1000000007;
    
public:
    int solve(int n, vector<int>& portal) {
        vector<long long> dp(n + 2, 0);
        
        // 动态规划计算每个房间的移动次数
        for (int i = 2; i <= n + 1; ++i) {
            dp[i] = (2 * dp[i-1] - dp[portal[i-1]] + 2) % MOD;
        }
        
        // 处理负数取模的情况
        long long result = dp[n + 1];
        return result < 0 ? result + MOD : result;
    }
};

int main() {
    int n;
    cin >> n;
    
    vector<int> portal(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> portal[i];
    }
    
    Solution solution;
    cout << solution.solve(n, portal) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        private static final long MOD = 1000000007;
        
        public int solve(int n, int[] portal) {
            long[] dp = new long[n + 2];
            
            // 动态规划计算每个房间的移动次数
            for (int i = 2; i <= n + 1; ++i) {
                dp[i] = (2 * dp[i-1] - dp[portal[i-1]] + 2) % MOD;
            }
            
            // 处理负数取模的情况
            long result = dp[n + 1];
            return (int)(result < 0 ? result + MOD : result);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] portal = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            portal[i] = sc.nextInt();
        }
        
        Solution solution = new Solution();
        System.out.println(solution.solve(n, portal));
        
        sc.close();
    }
}

class Solution:
    def solve(self, n, portal):
        MOD = 1000000007
        dp = [0] * (n + 2)
        
        # 动态规划计算每个房间的移动次数
        for i in range(2, n + 2):
            dp[i] = (2 * dp[i-1] - dp[portal[i-1]] + 2) % MOD
            
        # 处理负数取模的情况
        result = dp[n + 1]
        return result if result >= 0 else result + MOD

# 读取输入
n = int(input())
portal = [0] + list(map(int, input().split()))

solution = Solution()
print(solution.solve(n, portal))