競プロ典型90問 019 Pick Two(★6)
この問題は典型的な区間DPの問題である. $ dp_{l, r} := $ A_l, A_{l + 1}, ..., A_{r - 1}を取り除くのに必要な最小のコスト とすると, 次のような遷移で解くことができる.
$ r - l \leq 1のとき
この場合, $ dp_{l, r}は無限大とする(どうやっても取り除くことができない).
$ r - l = 2のとき
この場合, $ dp_{l, r} = |A_l - A_{l + 1}|となる.
それ以外のとき
次の2つの遷移をすればよい.
1. 最後に人$ l, r - 1が抜ける場合 → $ dp_{l, r} = max(dp_{l, r}, dp_{l + 1, r - 1} + |A_l - A_{r - 1}|)
2. それ以外の場合 → $ dp_{l, r} = max(dp_{l, r}, dp_{l, i} + dp_{i, r})
よって, この問題をメモ化再帰により$ O(N^3)で解くことができた.