問題はこちら
問題概要
長さの数列の最長増加部分列は何通りあるか求めよ.思考の流れ
すぐ思いつくのが最後にをとったときの番目まででのLISの取り出し方の総数, としたDP
サンプル1(1 4 2 5 3)だとみたいになる.
このDPの更新式は,最後にをとったときの番目まででのLIS長として,
となる. の条件がなければ, BITを用いての小さい方から見ていくいつものやつで解ける.
の条件があっても同様にの値ごとにBITを作成して, の更新の際にのBITを参照すればよい. BITのサイズの和はであるので計算量も大丈夫.