CF407B Long Path

https://www.luogu.org/problemnew/show/CF407B

递推。

设$f_i$表示从第$i-1$个房间到第$i$个房间所需要的步数。

经过观察可得,到达第$i$个房间时，前$i-1$个房间一定经过了偶数次。

那么$f_i$等于1(从$i-1$走到$i$)+1(到了$i$后走到$p_i$)+$\sum _{j=p_i}^{i-1}$(从$p_i$走回i)

最后把所有的$p_i$加起来即可

#include <iostream>

using std::cin;
using std::cout;
using std::endl;
using int_t = long long int;

const int_t mod = 1000000007;
const int_t LARGE = 1000;

int_t seq[LARGE + 1];
int_t dp[LARGE + 1];
int_t n;
int main()
{
    cin >> n;
    for (int_t i = 1; i <= n; i++)
    {
        cin >> seq[i];
    }
    dp[0] = 1;
    for (int_t i = 1; i <= n; i++)
    {
        dp[i] += 1 + 1;
        for (int_t j = seq[i]; j < i; j++)
        {
            dp[i] += dp[j];
            dp[i] %= mod;
        }
        dp[i] %= mod;
    }
    int_t result = 0;
    for (int_t i = 1; i <= n; i++)
    {
        result += dp[i];
        result %= mod;
    }
    cout << result << endl;
    return 0;
}