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; }