Traced

クラス · 経路つき DP 値 (Traced)

template <class T, class Label = int>
struct Traced;

概要

経路を相乗りさせたDPの値

比較は cost のみで行い、経路は push が $O(1)$ の永続スタックで保持する。そのため経路を持ち回っても比較コストは増えず、DPの時間計算量は変わらない。遷移のたびに then(w, label) でラベルを積み、最後に to_vector() で始点から終点の順に取り出す。遷移元を記録する配列と復元ループが不要になる。

テンプレートパラメータ

名前	説明
`T`	コストの型。`operator<=>` と `operator+` を持つこと。
`Label`	経路に積むラベルの型（頂点番号・選んだ添字など）

備考

メモリは then の結果を採用した回数に比例し、永続スタックのノードは解放されない。状態数が非常に多いDPでは、遷移元を記録する方式のほうがメモリで有利になる。

構築・破棄

名前	説明	計算量
`(constructor)`	(1) コストを `T()`、経路を空にして構築する (2) コストを指定し、経路を空にして構築する (3) コストと経路を直接指定して構築する	$O(1)$

メンバ関数

名前	説明	計算量
`then`	コストに w を足し、経路に label を積んだ値を返す	$O(1)$
`size`	積んだラベルの個数を返す	$O(1)$
`to_vector`	積んだラベルを積んだ順（始点から終点）に返す	経路長を $L$ として $O(L)$

演算子

名前	説明	計算量
`operator<=>`	`cost` のみで比較する	$O(1)$
`operator==`	`cost` のみで比較する	$O(1)$

メンバ型

名前	説明	計算量
`value_type`	コストの型	型エイリアスで実行時計算量はない
`label_type`	ラベルの型	型エイリアスで実行時計算量はない
`path_type`	経路を保持する永続スタックの型	型エイリアスで実行時計算量はない

メンバ変数

名前	説明	計算量
`cost`	比較に使うコスト	$O(1)$ で参照可能
`path`	積んだラベルの列（先頭が最後に積んだラベル）	$O(1)$ で参照可能

メンバの詳細

(constructor)

// (1)
constexpr Traced();

// (2)
constexpr explicit Traced(T _cost);

// (3)
constexpr Traced(T _cost, path_type _path);

(1) コストを T()、経路を空にして構築する

計算量: $O(1)$

(2) コストを指定し、経路を空にして構築する

計算量: $O(1)$
備考: 経路の情報を落とさないよう暗黙変換にはしていない。

(3) コストと経路を直接指定して構築する

then では表せない結合（max(cost, w) を使うボトルネック最短路など）は Traced(std::max(dp[i].cost, w), dp[i].path.push(label)) のように直接組む。

計算量: $O(1)$