codeforces D. Long Path

http://codeforces.com/contest/408/problem/D

题意：有一排房间每个房间有两扇门，一扇通往第i+1个房间，另一扇通往第p[i]个房间，（p[i]<=i）然后他每经过一个房间就做一个标记，只有偶数个标记时他才会走第一扇门。问你他走到第n+1个房间需要多少单位时间。

思路：dp，一个人进入一个房间之后，如果标记为奇数的话，他会进入p[i]房间，又重新进入这个房间，重复一次的过程，所以dp[i]=dp[i-1]+dp[i-1]-dp[p[i]-1]+2;

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 100010
 5 using namespace std;
 6 const int mod=1000000007;
 7 
 8 long long dp[maxn];
 9 int p[maxn];
10 int num[maxn];
11 int n;
12 
13 int main()
14 {
15     scanf("%d",&n);
16     for(int i=1; i<=n; i++)
17     {
18         scanf("%d",&p[i]);
19     }
20     dp[1]=2;
21     for(int i=2; i<=n; i++)
22     {
23        if(i==p[i])
24        {
25            dp[i]=dp[i-1]+2;
26        }
27        else
28        {
29            dp[i]=(dp[i-1]+dp[i-1]-dp[p[i]-1]+2+mod)%mod;
30        }
31     }
32     printf("%lld
",dp[n]);
33     return 0;
34 }

View Code