P7537 [COCI2016-2017#4] Rima（トライ木と木上の動的計画法）
P7537 [COCI2016-2017#4] Rima
トライ木と木上の動的計画法
問題の制約を整理すると、文字列の末尾に文字を追加したり、置換したり、削除したりできることが分かります。この操作は、あるポイントで削除が起こり、その後追加が続くため、単峰性を持ちます。両端の処理は対称なので、片側だけ考えれば十分です。文字列を逆転させてトライ木に挿入し、木上のDPで各ノードの部 ...
9月15日 19:50 投稿