Ecasdqina's MEMO

Ecasdqina's MEMO.

メモ帳.

Don't Be a Subsequence 典型解説

問題

E - Don't Be a Subsequence

本文

問題文に最も短いものと書かれているので与えられた文字列から構成する文字列の長さを得られないかを考えます, これは自明な考察をすることで動的計画法から得ることが出来ます.
ここで動的計画法の結果から復元をするというテクを思い出せばあとはやるだけで構成を完了することができます.

動的計画法 -> 構築 という流れはかなり典型でかつ高難度の問題にもよく見られるので覚えておくと良いテクのひとつです.

コード

Submission #2449563 - AtCoder Regular Contest 081