A = (3 1 4 1 5) 部分列 (1 4) : OK (1 5) : NG 1を取り出した位置が2文字目か4文字目か特定できない (1 1 5): OK
問題内容と制約からDPっぽいのは察せるが、どこから遷移できて、どこから遷移してはいけないかを明確にしないと混乱する。
実際は $i$ の次元は省略して $j$ だけで実装する。
また、indexは0からに読み替えて説明する。
$i$ の昇順に更新していく。
$i$ を進めても、$j$ は基本的に $DP[i][j] = DP[i-1][j]$ となり引き継がれるので、$i$ の次元を省略していたら特に何もしなくていい。
$DP[i][i]$ だけ新しく計算する。
最後に使った位置が $j=0~i-1$ からそれぞれ遷移できて、また $A_i$ を先頭とする部分列が新たに1つ加わる。
これを計算していくと $1,2,4,8,...$ と2の冪乗となる。 仮に $A$ に出てくる要素に重複が無ければ、この総和が答えとなる。
重複があると、一意に特定できない場合が出てくる。
i 0 1 2 3 4 5 6 7 8 9 A 3 1 4 1 5 9 2 6 5 3 ^ i=8 において、この5を使う場合、 ~~~~~~~ ^ i=4 より手前から遷移すると、この5と区別できなくなる また、A8を先頭としても同様に区別できなくなる
そのため、過去に同じ値が出てきた要素については、直前に同じ値が出現したindexを $p$ として、$p$ 未満から遷移できない。
$j$ の和を取る開始indexが変わり、また最後の +1 もなくなる。
上記だけだと、$(5,3)$ のような条件を満たさないケースが数えられてしまう。
つまり、$i=9$ において $DP[9][9]$ を求めるとき、今のままだと波線部全体の $DP[8][j]$ の総和を取ることになる。
i 0 1 2 3 4 5 6 7 8 9 A 3 1 4 1 5 9 2 6 5 3 ~~~~~~~~~~~~~~~~~
しかしこの中には複数の同じ値 $5$ などが挟まれていて、 このままだとどちらの $5$ が最後だったケースからも遷移されてしまい、区別できなくなる。
同じ値に関しては最後に出現した位置、この場合は $5$ に関して $j=4$ は除外して $j=8$ からのみ遷移したい。
i 0 1 2 3 4 5 6 7 8 9 A 3 1 4 1 5 9 2 6 5 3 ~ ~~~ ~~~~~~~
要は、$DP[○][j]$ の値は、$A_j$ と同じ値が次に出てくる位置を $n$ として、$DP[n+1以降][n+1以降]$ に遷移してはいけない。
i 0 1 2 3 4 5 6 7 8 9 10 11 A 3 1 4 1 5 9 2 6 5 3 5 8 ^ i=4のDPの値は ^ xxxxxxx 次に同じ値が出てくるi=8より後に遷移してはいけない
$i=8$ の時点で、$DP[8][8]$ の値を計算した後に $DP[8][4]$ の値を0に更新しておけば、これを達成できる。
これで $DP$ が正しく求められ、最後まで処理したら $DP[N-1]$ の総和が答えとなる。
区間の和を頻繁に求めるため、DP配列自体を Segment Tree や Fenwick Tree などで実装すれば、$O(N \log{N})$ となる。
配るDPともらうDPの両面から条件に合わないものの除外を行う感じで、一方だけで考えているとなかなかたどり着かなかった。