附加题

<?php

fscanf(STDIN, '%d', $n);
$line = fgets(STDIN);
$arr = explode(' ', trim($line));
$count = 0;
$i = 1;
$costMap = array();//记录首次到达i房间所用的步数
$mod = 1000000007;
//每次循环进入一个新房间
while (true)
{
    if ($i == $n + 1)
        break;
    
    //第1次到达i房间，把count记录下。并且由1<=pi<=i可知：前面房间全部偶数次访问才能抵达该房间
    $costMap[$i] = $count;
    
    //传送门，步数+1，后面就相当于已经处于传送到位的房间了
    $transport = 1;
    
    //为了抵达i+1房间，需要再次回到i房间，计算要花的步数，前面的房间可以看做全都没有访问过，所以两次首次相减即可
    $again = $costMap[$i] - $costMap[$arr[$i - 1]];//有可能为负，因为mod的原因。有可能为0，因为已经传送到位的本来就可能是同一个房间
    
    //+1进入下一房间
    $count = ($count + $transport + $again + 1) % $mod;
    $i++;
}
if ($count < 0)
    $count += $mod;
echo $count. PHP_EOL;

• 仔细分析 1<=pi<=i 知道用动态规划做。
• 记录第一次到达i为dp[i]，此时前面的所有门肯定是已经到达偶数次了
  • 因为传送只会后退，前进的唯一方式是偶数次到达并+1，不能跳跃
  • 所以到达i门前面所有门都走过并且经过偶数次（反正法也可以证明）
• dp[i]=dp[i-1]+第二次到达i-1 + 1
• 第一次到达i-1门后再走一步会回到p[i-1]，此时p[i-1]门到达奇数次，其他所有门到达偶数次
• 这和第一次到达p[i-1]门的情况完全相同，所以从p[i-1]门回到i-1门，需要dp[i-1]-dp[p[i-1]]
• 所以dp[i] = dp[i-1] + dp[i-1] - dp[p[i-1]] + 1 + 1
• dp[i] = 2 * dp[i-1] - dp[p[i-1]] + 2

#include <iostream>
using namespace std;

long long p[1001], dp[1001], n;
const long long mod = 1e9 + 7;

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

• 感谢Abtt指正，已经修改过来

let n = parseInt(readline().trim());
let roomArr = readline().trim().split(" ");
let mod = 1000000007
let dp = new Array(n+2);
dp[1] = 0
for(let i = 2;i<=n+1;i++){
    dp[i]=2*dp[i-1]+2-dp[roomArr[i-2]]
    if(dp[i]<0){
        dp[i] += mod;
    }else if (dp[i] >= mod){
        dp[i] %= mod;
    }
}
console.log(dp[n+1])

#include<iostream>
#include<vector>

using namespace std;

const long long int mod = 1e9 + 7;
int main()
{
    int n;
    cin >> n;
    vector<int>p(n+1, 0);
    for(int i = 1; i <= n; i++)
    {
        cin >> p[i];
    }
    
    vector<int>dp(n+2, 0);//记录第一次到达i为dp[i]
    dp[1] = 0;
    for(int i = 2; i<= n+1; i++)
    {
        dp[i] = (2*dp[i - 1] - dp[p[i - 1]] + 2) % mod;
    }
    cout << (dp[n + 1] < 0 ? dp[n + 1] + mod : dp[n + 1]);
    return 0;
}

//直接求解可以通过60%
    public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        int roomNum=in.nextInt();
        int[] visitedNum=new int[roomNum];
        int[] transferDoor=new int[roomNum];
        for(int i=0;i<roomNum;i++)
        {
            transferDoor[i]=in.nextInt()-1;
        }
        int movingCount=0;//移动次数
        
        //从第一个房间开始 第一个房间已经过问过一次
        visitedNum[0]=0;
        int roomID=0;
        while(roomID!=roomNum)
        {
             visitedNum[roomID]+=1;
            movingCount++;
            if(visitedNum[roomID]%2==0)
            {
                roomID+=1;
            }
            else
            {
                roomID=transferDoor[roomID];
            }
        }
        System.out.println(movingCount%1000000007);
    }

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

const int M = 1e9+7;

int main(){
    int n;
    scanf("%d", &n);
    int a[n], dp[n+1];
    memset(dp, 0, sizeof(dp));
    for(int i=0;i<n;i++)
        scanf("%d", &a[i]);
    for(int i=1;i<=n;i++)
        dp[i] = (2*dp[i-1]%M - dp[a[i-1]-1]+2) % M;
    printf("%d\n", dp[n]);
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
long long p[N], f[N];
int n,res;
int main() {
    cin >> n;
    // 只会往做走 往又走只有靠走了奇数次
    for(int i = 1; i <= n; ++ i) {
        cin>>p[i];
    }
    // 我们要求到n + 1需要走多少次
    // 可以求子问题 第二次走到n需要走多少次
    // 子问题 第二次走到n - 1需要走多少次
    // f[i] 如何 由 f[i - 1] 转移过来？
    // 我们假设f[i]记录的是到达i两次需要的次数
    // f[i - 1] + 1 次到达i第一次
    // 然后i走到p[i] p[i]再次走到i需要多少次
    // p[i] 走到 i - 1 
    // 综上f[i] 表示第二次进入i需要的行程数
    f[0] = 0;
    for(int i = 1; i <= n ; ++i) {
        // f[i] += f[i - 1] + 1; 
        int j = p[i];
        // f[i] += (f[i - 1] - f[j - 1] + 1);
        f[i] = (2*f[i - 1] - f[j - 1] + 2) %mod;
    }
    cout<<(f[n] + mod ) % mod<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ps = new int[n + 1];
        int index = 1;
        while (index <= n) {
            ps[index ++] = sc.nextInt();
        }
        long[] dp = new long[n + 1];
        dp[0] = 0L;
        dp[1] = 2L;
        for (int i = 2; i <= n; i ++) {
            dp[i] = 2 * dp[i - 1] - dp[ps[i] - 1] + 2;
            dp[i] =  dp[i] < 0 ? dp[i] + 1000000007 : dp[i] % 1000000007;
        }
        System.out.println(dp[n]);
    }
}

n=int(input())
pi=list(map(int,input().split()))
dp=[0 for i in range(n+1)]
for i in range(1,n+1):
    #dp[i]第一次到i所需的移动次数，此处的i就是n+1
    dp[i]=(dp[i-1]+(dp[i-1]+1-dp[pi[i-1]-1])+1)%1000000007
print(dp[-1])

const ll mod = 1000000007;
ll dp[1010];//对于一个点从偶次状态到偶次状态的最小步数
int p[1010];
int n;

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> p[i];
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        if(p[i] == i){
            ans = (ans + 1ll * 2) % mod;
            dp[i] = 1ll * 2;
        }
        else{
            ll now = 0;
            for(int j = p[i]; j < i; j++){
                now = (now + dp[j]) % mod;
            }
            (now = now + 2ll) % mod;
            dp[i] = now;
            ans = (ans + now) % mod;
        }
    }
    cout << ans << "\n";
}