問題はこちら
問題概要
個の正整数からなる数列が与えられる.とを満たす異なる数列であってを満たすものが存在するか判定し,存在するならばつ出力せよ.解説
の要素を「に振り分ける」,「に振り分ける」,「どちらにも振り分ける」とすればいけそう.を管理するDPをすればいい.ただし,つの振り分け方のうち少なくともつを行う必要がある.結局,持つべき状態は「の何番目を見てるか」「」「つの振り分け方のどれを使用したか」.
経路復元も頑張ってする.経路復元の例
計算量はをmodとして
問題はこちら
結局,持つべき状態は「の何番目を見てるか」「」「つの振り分け方のどれを使用したか」.
経路復元も頑張ってする.経路復元の例
計算量はをmodとして