Struct nekolib::algo::Larsch

pub struct Larsch<T, F, W> { /* private fields */ }

LARSCH algorithm。

$E[i] = F[j] + W(j, i)$ ($0\le j<i<n$) と書ける DP を計算する。 ここで、$F[j]$ は $E[j]$ から高速に計算できる値とし、$W$ は concave QI を満たすとする。

todo!() ちゃんと書く

$\gdef\DP{\operatorname{dp}}$ 行列 $M[i, j]$ は、$\DP[j]$ から $\DP[i]$ に遷移するときのコストを表し、 値がオンラインに定まる。この行列は concave totally monotone になっている。

この行列の row minima を求めるのに相当する。

(argmin, min): (Vec<usize>, Vec<T>) を返すので、i = n - 1 から始めて argmin[i] -> i の遷移を辿ることで復元も可能。

Notes

SMAWK のオンライン版。SMAWK もそのうち書く。

Examples

use nekolib::algo::Larsch;

let a = vec![1_i64, 2, 3, 4, 5];
let c = 6;
let n = a.len();

let map = |&x: &i64| x;
let trans = |il: usize, ir: usize| (a[il] - a[ir]).pow(2) + c;
let (argmin, min) = Larsch::new(n - 1, n - 1, 0, map, trans).solve();

assert_eq!(argmin, &[0, 0, 0, 0, 2]);
assert_eq!(min, &[0, 7, 10, 15, 20]);

愚直に書いたときの DP がどんな感じかを書いておくと役立つ場合がありそう。todo!()

Complexity

$E[\bullet]$ の計算を $O(1)$ time として $O(n)$ time。

References

• Larmore, Lawrence L., and Baruch Schieber. “On-line dynamic programming with applications to the prediction of RNA secondary structure.” Journal of Algorithms 12, no. 3 (1991): 490–515.

See also

• https://noshi91.github.io/Library/algorithm/larsch.cpp

Applications

Examples にある EDPC-Z の例の他、AOJ 3086 などにも利用できる。

use std::cmp::Reverse;

use nekolib::{algo::Larsch, ds::N1Rmq};

let a = vec![1, 1, 5, 5, 1, 1];
let l = 2;
let n = a.len();

let a: Vec<_> = a.into_iter().map(|ai| Reverse(ai)).collect();
let rmq: N1Rmq<_> = a.into();
let oo = 10_i64.pow(18);

let map = |&x: &i64| x;
let trans = |il: usize, ir: usize| {
    if ir < il + l { oo } else { -rmq.min(il, ir).0 }
};
let (argmin, min) = Larsch::new(n, n, 0, map, trans).solve();
let max: Vec<_> = min.into_iter().map(|x| -x).collect();

assert_eq!(argmin, &[0, 0, 0, 0, 2, 3, 3]);
assert_eq!(max, &[0, -oo, 1, 5, 6, 10, 10]);

Implementations

impl<T, F, W> Larsch<T, F, W>where F: Fn(&T) -> T, W: Fn(usize, usize) -> T, T: Add<Output = T> + Ord,

pub fn new(n: usize, m: usize, init: T, map: F, trans: W) -> Self

pub fn solve(self) -> (Vec<usize>, Vec<T>)