Struct nekolib::algo::Larsch

source ·
pub struct Larsch<T, F, W> { /* private fields */ }
Expand description

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

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§

source§

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

source

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

source

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

Auto Trait Implementations§

§

impl<T, F, W> !RefUnwindSafe for Larsch<T, F, W>

§

impl<T, F, W> !Send for Larsch<T, F, W>

§

impl<T, F, W> !Sync for Larsch<T, F, W>

§

impl<T, F, W> Unpin for Larsch<T, F, W>

§

impl<T, F, W> !UnwindSafe for Larsch<T, F, W>

Blanket Implementations§

source§

impl<T> Any for Twhere T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for Twhere T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for Twhere T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for Twhere U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<V, T> VZip<V> for Twhere V: MultiLane<T>,

§

fn vzip(self) -> V