別解です.ほぼ一緒なので丁寧には書きません.
問題はこちら
問題概要
を並び替えてできる数列で,以下の条件を満たすものの数を求めよ.- を満たす全ての数列について,の中に以下の数は個以下しか存在しない.
解説
公式解説では数列を左端から決めて,使った数を状態として持つDPをしていましたが,小さい数から位置を決めていくことを考えます.DPでは数列中の既に決まった位置を持っておきます.すると遷移は- (条件を満たさない時)
- (条件を満たすとき)
となります.条件を満たすかを見るときはとなる条件のみを見ればいいです.この方針だと任意の区間(位置)の条件でも解くことができるはず(たぶん).