Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【Educational DP-Q Flowers】単調増加=小さい方から入れていく

気づくのに1時間以上かかりました。典型なので次は瞬見えしたい。

Q - Flowers

問題

花がN本並んでいる。それぞれ高さhi,価値aiである。

このうち高さが単調増加になるように何本かをとり、価値の和を最大化したい。その和を求めよ。

制約: N=105, hiは1からNで相異なる

方針

単調増加というのをどう捉えるかが問題です。

私の第一感は、ある花iで左右に分割した時に、左はh<hiの最大和、右はh>hi以上の最大和となり、問題が分割出来るのではと思いましたが、解けそうなものの、たぶん計算量が高すぎます。

正しい考え方は、この花を高さの低い順に入れていきます。

f:id:akiradeveloper529:20190928123622j:plain

何らかの値についてソートして、データ構造に対してぶちこんでいくことで、ある時にはそれより小さい(あるいは大きい)データしか入っていないことになります。

この考え方自体は典型で、

【yukicoder No.877 Range ReLU Query】2つの汎用的な解法 - Rustコトハジメ

のbeet法でも見ることが出来ます。

例えば、赤を入れる時には、赤の場所より前の最大値をとるのが最善ですし、青を入れる時には青より前の最大値をとるのが最善(例えば、一番低い花の価値が超高ければ、それがとれるでしょう)です。

区間の最大値をとるのは、セグメントツリーで実装出来ます。

実装

fn solve() {
    input!{
        N:usize,
        h:[i64;N],
        a:[i64;N],
    }
    let mut ha = vec![];
    for i in 0..N {
        ha.push((h[i],a[i],i));
    }
    // hが小さい順に入れていけば、
    // あるhを訪れた時に、segにはそれ未満のhの情報しか入ってない
    ha.sort();
    // seg[0,i] := 高さh未満でiより前の最大a和
    let mut seg: SEG<MAX> = SEG::new(N);
    for (h,a,i) in ha {
        let ma = seg.query(0,i);
        seg.update(i,ma+a);
    }
    println!("{}",seg.query(0,N));
}

考察

単調増加とかそういうワードに対して、とりあえずソートとして小さい順に入れていくという図を脊髄反射的に想像したいです。