けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

二次元ナップサックDP

AtCoder AGC 021 D - Reversed LCS (900 点)

面白かった 問題へのリンク 問題概要 文字列 が与えられる。あらかじめ文字列の中の 文字を自由に変更することができる。 こうして得られた文字列と、それを反転した文字列の LCS (最長共通部分列) の長さとして考えられる最大値を求めよ。 制約 考えたこと …