[模拟赛] 过关（pass）

前言：

我做不出 \(T1\) 我活鸡蛋。/kk

题目描述：

有 \(n+1\) 关卡，有一个机器人从关卡 \(1\) 开始闯关，每个关卡里有一个陷阱。机器人没有第 \(i\) 关的经验时会回到第 \(pi\) 关重新闯一遍，并获得了这一关的经验。

有经验时机器人会直接到达下一关。由于机器人太笨了，所以通过一关后他会认为这一关的经验没用了，从而忘掉它。

请你算出机器人需要多少次才能到达终点？

解题思路：

设计状态 \(f_{i}\) 表示通过关卡 \(i\) 所需要的步数，那么从 \(i-1\) 到 \(i\) 所经过的步骤应该是 \(i-1 \rightarrow i \rightarrow p_{i} \rightarrow i-1 \rightarrow i\)。所以转移应为 \(f_{i}=f_{i-1}+1+(f_{i-1}-f_{a_{i}}+1)\)。

代码实现:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, f[N];
signed main(){// freopen("pass.in", "r", stdin);// freopen("pass.out", "w", stdout);cin >> n;for(int i = 1, x; i <= n; i++) cin >> x, f[i] = f[i - 1] + 1 + (f[i - 1] - f[x - 1] + 1 + mod) % mod, f[i] %= mod;cout << f[n] << endl;return 0;
}