Rustコトハジメ

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

【Educational DP-B Frog 2】初歩的DP。DAGをかんじる

Aの一般化です。AはK=2の時でしかないため省略します。

B - Frog 2

問題

長さNのhiが与えられます。かえるは今、i=1にいます。そこから、i+1,i+2,...i+Kにジャンプ出来ます。ジャンプする先をjとすると、|hj-hi|のコストがかかります。

i=Nにたどり着くコストの最小値を求めよ。

制約: N=105, K=102

方針

DPの基本形です。

iにたどり着く遷移を考えると、i-1,i-2,..i-Kにいたことになります。つまり、mincost(i) = min { mincost(i-x) + cost(i-x, i) } という式が成り立ちます。

これをグラフにします。ここで、辺のコストをcost(i,j)とします。

f:id:akiradeveloper529:20190930180410j:plain

するとこれは、グラフの話とすると、ノード1からノードNへの最短距離となります。従って、プライオリティキューを使ったダイクストラ法でも解けます(もしかしたらTLEするかも)。しかし今回はDPで解きます。

mincost(N)を求めるためには実直に上の式を関数に落として、関数mincostをメモ化再帰で実装するという考え方でもいいです。これはもらうDPの一種です。

逆に、ノードiを訪れた時にはすでにmincost(i)が確定しているという性質を利用して、mincost(i+1)からmincost(i+K)に最小値候補を与えて更新するというのも一つの手です。結局、iを上げていった時にはこの候補が全部出揃うことになりますから、この方法でも求まります。これを、配るDPといいます。今回はこちらで実装してみましょう。

実装

計算量はO(KN)です。

fn solve() {
    input!{
        N:usize,K:usize,
        h:[i64;N],
    }

    let mut dp=vec![std::i64::MAX; N];
    dp[0]=0;
    for i in 1..N {
        let mut minv=std::i64::MAX;
        for k in 1..K+1 {
            if i>=k { //i-k>=0
                minv=min(minv,dp[i-k]+i64::abs(h[i]-h[i-k]));
            }
        }
        dp[i]=minv;
    }
    println!("{}",dp[N-1]);
}