Codeforces 408D Long Path (DP)

題目：

One day, little Vasya found himself in a maze consisting of?(n?+?1)?rooms, numbered from?1?to?(n?+?1). Initially, Vasya is at the first room and to get out of the maze, he needs to get to the?(n?+?1)-th one.

The maze is organized as follows. Each room of the maze has two one-way portals. Let's consider room number?i?(1?≤?i?≤?n), someone can use the first portal to move from it to room number?(i?+?1), also someone can use the second portal to move from it to room number?pi, where?1?≤?pi?≤?i.

In order not to get lost, Vasya decided to act as follows.

• Each time Vasya enters some room, he paints a cross on its ceiling. Initially, Vasya paints a cross at the ceiling of room?1.
• Let's assume that Vasya is in room?i?and has already painted a cross on its ceiling. Then, if the ceiling now contains an odd number of crosses, Vasya uses the second portal (it leads to room?pi), otherwise Vasya uses the first portal.

Help Vasya determine the number of times he needs to use portals to get to room?(n?+?1)?in the end.

?

Input

The first line contains integer?n?(1?≤?n?≤?103)?— the number of rooms. The second line contains?n?integers?pi?(1?≤?pi?≤?i). Each?pi?denotes the number of the room, that someone can reach, if he will use the second portal in the?i-th room.

?

Output

Print a single number — the number of portal moves the boy needs to go out of the maze. As the number can be rather large, print it modulo?1000000007?(109?+?7).

?

Examples

input

2
1 2

output

4

input

4
1 1 2 3

output

20

input

5
1 1 1 1 1

output

62

---

題意：
如果當前到達點i的進入次數cnt為奇數 則可以到達p[i]位置 如果是偶數 可以到達i+1位置 求從1走到n+1需要的總步數 

思路：
第一次走進i房間的進入次數cnt為1 是奇數 會往后退回p[i]位置 但是此刻p[i]位置的cnt也變成了奇數 因為當時只有為偶數才能向前走 那么會退回到p[p[i]]位置 不斷遞歸
因此 dp[i]記為走到當前位置需要的總步數 狀態轉移方程為dp[i+1]=dp[i]+1+(dp[i]-dp[p[i]])+1 即為dp[i+1]=2*dp[i]-dp[p[i]]+2

---

代碼：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int maxn=1e3+10;
const int mod=1e9+7;
int n;
int p[maxn];
ll dp[maxn];int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&p[i]);}dp[1]=0;for(int i=1;i<=n;i++){dp[i+1]=(2*dp[i]-dp[p[i]]+2+mod)%mod;}printf("%lld\n",(dp[n+1]+mod)%mod);return 0;
}

?