【Codeforces Round #239 (Div. 1) B】 Long Path

在这里输入题意

【题解】

DP,设f[i]表示第一次到i这个房间的时候传送的次数。
f[1] = 0,f[2] = 2
考虑第i个位置的情况。
它肯定是从i-1这个位置走过来的。
但是第一次走到i-1这个位置的时候。
需要再走回p[i-1],然后回到i-1才能再走到i
其实这个时候走到p[i-1]的时候,我们就和第一次走到p[i-1]的时候是一样的。
因此再从p[i-1]走到i-1的话。
它的移动次数就等于f[i-1]-f[p[i-1]]
那么
f[i] = f[i-1]+1+f[i-1] - f[p[i-1]] + 1

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3;

const int MOD = 1e9+7;

int n,p[N+10],f[N+10];

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    cin >> n;

    for (int i = 1;i <= n;i++) cin >> p[i];

    f[1] = 0;f[2] = 2;

    for (int i = 3;i <= n+1;i++){

        f[i] = ((f[i-1] + 1 + f[i-1]-f[p[i-1]] + 1)%MOD+MOD)%MOD;

    }

    cout<<f[n+1]<<endl;

	return 0;

}

巴特西

【Codeforces Round #239 (Div. 1) B】 Long Path

最新文章

热门文章