コンテストの解説見たら解けました。
最初は「最適性の原理」に基づいてDPテーブルにおけるdp[i][j]に、0からi-1番目の文字列sと、同じく0からj-1番目の文字列tという2つの文字列のlcs(最長共通部分列)を格納していく方式をとって組んでたらWAは無かったけれどTLEが来ました。そこからは解説記事も参考にlcsの長さを格納するdpテーブル作った後にそれを遡るように解析していくやり方とったところACでした。
次の問題は......、有向グラフですね(解いたことはない)
コンテストの解説見たら解けました。
最初は「最適性の原理」に基づいてDPテーブルにおけるdp[i][j]に、0からi-1番目の文字列sと、同じく0からj-1番目の文字列tという2つの文字列のlcs(最長共通部分列)を格納していく方式をとって組んでたらWAは無かったけれどTLEが来ました。そこからは解説記事も参考にlcsの長さを格納するdpテーブル作った後にそれを遡るように解析していくやり方とったところACでした。
次の問題は......、有向グラフですね(解いたことはない)