Codeforces Round #239 (Div. 2)_Long Path_html/css_WEB-ITnose

Question link

Question meaning:
Enter n values, indicating that there is an edge between the current point and the input point (associated point). Initially starting from 1, when reaching a point, the point value is increased by one. If the value at this time is an odd number, then it will go to the associated point, otherwise it will reach the adjacent point on the right
Find how much to transfer when reaching n 1 Times

Analysis:
Consider the situation when you first arrive at point P. The value of each previous point must be an even number (you can only come from the previous point, and only when the value is an even number to go right). At this time, because the value of the current point is an odd number, it will reach the associated point Q (must not be on the right side of the current point). Then if you want to reach the next point, you must continue from point Q to point P, and the situation at this time is the same as The situation from the beginning to point Q is exactly the same (even values ​​and zero are obviously equivalent), that is, the sub-problem

is obtained. Understanding:
Although the state transition of this question is not a DAG, It can be found that the transfer is conditional, and when looking back from the current point, you can only reach the previous state, so you can consider DP
Similarly, the key to DP is how to deal with this "loop"

const int MAXN = 1100;int ipt[MAXN], dp[MAXN];int main(){//    freopen("in.txt", "r", stdin);    int n;    while (~RI(n))    {        CLR(dp, 0);        FE(i, 1, n) RI(ipt[i]);        FE(i, 1, n)        {            dp[i + 1] = (2 * dp[i] % MOD + MOD + 2 - dp[ipt[i]]) % MOD;        }        WI(dp[n + 1]);    }    return 0;}