yukicoder No.992 → 問題リンク
writerの解説とは違う方法で解いた。
#####問題
数列の最長増加部分列(LIS)の個数を求める問題。
ただし数列には同じ値があるかもしれない。
#####事前知識
$1, 2, \dots N$ の順列 $P_1, P_2, \dots P_N$ のLISの長さを求めるには、次のようなDPをすればよい。
・$dp[i] = P_i$ を最大値(最右項)とするLISの長さ
・$dp[i]$ は $P_i$ の小さい順に更新する。未更新の値については $dp[j]=0$ とする。
・$dp[i] = \max(dp[0], dp[1], \dots , dp[i-1])+1$ になる。この計算はBITを使えばよい。
個人的には、このやり方はDP配列を二分探索して値を更新するやり方よりも直感的で分かりやすいと思う。
#####解説
相異なるとは限らない数列というのが厄介だが、同じ値が2度採用されることはないのを考えると、$(A_i, -i)$ の小さい順に $1, 2, \dots N$ と値を付け替えればよいことがわかる。
これで、$1, 2, \dots N$ の順列($P_1, P_2, \dots P_N$ とする)のLISの個数を求める問題になった。
先ほどの 事前知識 の項に載せたLISの長さを求めるDPを応用する。
・$dpL[i] = P_i$ を最大値(最右項)とするLISの長さ
・$dpC[i] = P_i$ を最大値(最右項)とするLISの個数
・$dpL[i], dpC[i]$ は $P_i$ の小さい順に更新する。未更新の値については $dpL[j]=0, dpC[j]=0$ とする。
・$MAX=\max(dpL[0], dpL[1], \dots , dpL[i-1])$ とすると、$dpL[i]=MAX+1$、$ dpC[i]=\displaystyle\sum_{dpL[k]=MAX}dpC[k]$ と更新できる。この更新はBITなどを使えばよい。
実際の実装では、次のようにするとよい。
・$dpL[i]$ や $dpC[i]$ の代わりにstruct Item { int L; long long C; }; を作り、DP配列の要素はこの構造体にする。
・この構造体に関数Item max(Item a, Item b)を定義する。この関数は、aとbでLの値が異なる場合はLが大きい方の構造体を返し、Lの値が同じ場合はItem(a.L, a.C + b.C)を返す。
このように実装すると、事前知識 で述べたDPとほぼ同じようにDPの更新が書ける。