Codeforces ラウンド #239 (ディビジョン 2)_ロング パス_html/css_WEB-ITnose

質問リンク

質問の意味:
現在のポイントと入力ポイント (関連ポイント) の間にエッジがあることを示す n 値を入力します。最初は1から始まり、ある点に到達すると、ポイントの値が1ずつ増加します。このときの値が奇数の場合は、対応する点に移動します。それ以外の場合は、右側の隣接する点に到達します。 n+1 に達したときに何回転送する必要があるかを計算します

分析:

最初に点 P に到着したときの状況を考えてください。前の各点の値は偶数でなければなりません (前の点からのみ取得できます)値が偶数の場合のみ右に進むことができます)。このとき、現在の点の値は奇数であるため、関連する点 Q に到達します (現在の点の右側にあってはなりません)。次の点に到達したい場合は、続行する必要があります。点 Q から点 P まで、このときの状況は と同じです。 最初から点 Q までの状況はまったく同じです (値が偶数でゼロは明らかに等しい)、つまり部分問題が得られます。

理解:

この質問の状態遷移は DAG ではありませんが、遷移が条件付きであることがわかり、現在の時点から遡ると前の状態にしか到達できないため、DP を考慮できます
同様に、DPでもこの「リング」にどう対処するかが鍵となります

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