[CF407B] Long Path

18.10.24模拟赛T2。

一道简单的DP。当时推出了式子，但是有一个小地方推错了，忘记了减一。

于是怎么算都不对，就没再往这边考虑......

设f[i]为第一次到达i的时间。

显然f[i]=f[i-1]（先到达i-1）+1（又到了p[i-1]）+(f[i-1]-f[p[i-1]])（又回到i-1）+1（最后到了i）=2*f[i-1]-f[p[i-1]]+2。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define ll long long
 5 #define mod 1000000007
 6 using namespace std;
 7 
 8 int n;
 9 int p[1000005];
10 int f[1000005];
11 
12 int read()
13 {
14     int ret=0;char c=getchar();
15     while(c<'0'||c>'9')c=getchar();
16     while(c>='0'&&c<='9')ret=ret*10+c-'0',c=getchar();
17     return ret;
18 }
19 
20 int main()
21 {
22     scanf("%d",&n);;
23     for(int i=1;i<=n;i++)p[i]=read();
24     f[1]=1;
25     for(int i=2;i<=n+1;i++)
26         f[i]=((2*f[i-1]-f[p[i-1]]+2)%mod+mod)%mod;
27     printf("%d",f[n+1]-1);
28     return 0;
29 }