質問リンク
質問の意味:
現在のポイントと入力ポイント (関連ポイント) の間にエッジがあることを示す 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;}ログイン後にコピー
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
