0w1

CFR 407 B. Long Path ( DP )

Problem - B - Codeforces
題意:
給一排房間,其轉移點。第奇數次造訪某個房間時,會轉移到轉移點,否則向下一個房間移動。轉移點保證不在該房間之後。求最少要移動多少次,才會從起點移動到終點。
解法:
第一次 / 奇數次到某個房間 x 的時候,肯定第 x - 1 房間造訪偶數次了,能到達第 x - 1 房間,又意味著第 x - 2 房間也造訪偶數次了。因此可以得到結論,第奇數次到達某個房間所需的時間只需用該房間的編號就能確定。
dp[ i ] : 第一次到達 i - 1 號房間,要通至 i 號房間所需的時間
pdp[ i ] : 從始點到達第 i 房間所需的時間
dp[ i ] = 1 + pdp[ i ] - pdp[ P[ i ] ] + 1
pdp[ i ] = dp[ i ] + pdp[ i - 1 ]

int N;
vi P;

void init(){
    cin >> N;
    P = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> P[ i ],
        --P[ i ];
}

vi dp;
vi pdp;

void preprocess(){
    dp = pdp = vi( N + 1 );
    for( int i = 0; i < N; ++i ){
        ( dp[ i + 1 ] = pdp[ i ] - pdp[ P[ i ] ] + 2 ) %= MOD7;
        ( pdp[ i + 1 ] = pdp[ i ] + dp[ i + 1 ] ) %= MOD7;
    }
}

void solve(){
    if( pdp[ N ] < 0 )
        pdp[ N ] += MOD7;
    cout << pdp[ N ] << endl;
}