WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #189 Div2 E "Kalila and Dimna in the Logging Industry"

問題

http://codeforces.com/contest/320/problem/E

カリラとディムナは広大なジャングルに住む2頭のジャッカルだ。ある日彼らはお金を得るため、木の伐採工場に出向いた(?)。

伐採工場の社長は彼らにジャングルへ行き、a1, a2, ..., anの高さのあるn本の木を木って欲しいと頼んだ。彼らは店でチェーンソーを買った。チェーンソーを1回使うと木の高さを1だけ減らせる。だが、そのたびにチェーンソーのエネルギーを再充電せねばならない。充電のコストは切り終わった(高さが0になった)木のidに関係している。切り終わった木の最大のidがi(この木は最初高さがaiあったもの)だとすると、充電のコストはbiとなる。1つも切り終わっている木が無ければ、チェーンソーを再充電することはできない。チェーンソーは最初は充電されている状態である。i < jであれば、ai < aj であり、 bi > bj である事、bn = 0 であり、a1 = 1 が分かっている。カリラとディムナが全ての木をきり終える時の最小のコストを出力せよ。

制約

1 <= n <= 10^5
1 <= ai, bi <= 10^9



解放

こちらを参考にしましたm(_ _)m
Codeforces Round #189 Div1C Kalila and Dimna in the Logging Industry - sueki_1242の日記

自分の解説は結構省いてあります・・・

sueki_1242サンのブログにも書いてあるとおり、y = b[j] * x + dp[j]という直線が何本かあるから、x = a[i]の時、どの直線が一番最小になるの?という問題になります。


基本的にはこんな形になります。
f:id:Ekaing:20130701223307j:plain
jが大きくなればなるほど初期値は大きいですが、傾斜が緩やかになるかんじです。

もし現在考えている全ての線の最小値が、こんな感じで凸包であれば、
f:id:Ekaing:20130701223406j:plain

最小値は2つを見比べて(L2とL3)jが小さいほう(L2)の方が小さくなった時点で、最小値はL2で確定になります。
f:id:Ekaing:20130701223526j:plain
すぐに最小の線が分かるため、線の状態を凸包に保つ事が重要となります。

もしこんな線の状態で、
f:id:Ekaing:20130701223752j:plain

3本目の線を追加する時に、L1,L2の交点よりL2,L3の交点が右(x座標が大きい)にあれば、凸包の状態を保つ事ができます。
f:id:Ekaing:20130701224108j:plain

いわば、L2にも最小値をとるチャンスがまだあるよ!L2はまだ無駄な線じゃないよ!ってことです。
f:id:Ekaing:20130701224211j:plain

しかし、L1,L2の交点よりL2,L3の交点が左(x座標が小さい)となると、凸包の状態を保つ事ができず、
f:id:Ekaing:20130701224059j:plain

L2の線は無駄なばかりか間違った答えを生み出してしまいます。
f:id:Ekaing:20130701224321j:plain

よって、こうゆう場合、L2の線を除いてあげることが必要となります。


ソースコード

int n;
long long a[100050], b[100050], dp[100050];
int q[100050];

double f( int n, int m ){
    return (double)(dp[m] - dp[n]) / (b[n] - b[m]);
}

int main() {
    // 入力
    cin >> n;
    for( int i = 0; i < n; i++ ){
        cin >> a[i];
    }
    for( int i = 0; i < n; i++ ){
        cin >> b[i];
    }

    int s, e;
    s = e = 0;
    q[e++] = 0; 
    dp[0] = 0;

    // 線の状態は常に凸包状態となっている
    for( int i = 1; i < n; i++ ){
        // L1とL2を比べてL1<L2となるまで移動
        while( s + 1 < e && f( q[s], q[s+1] ) < a[i] ){
            s++;
        }

        // L1が最小値となる(凸包状態だから)
        dp[i] = dp[q[s]] + b[q[s]] * a[i];

        // L2 L3の交点 < L1 L2の交点となっていたら、L2を除く
        while( s + 1 < e && f( q[e-1], i ) < f( q[e-2], q[e-1] ) ){
            e--;
        }

        // L3を追加する
        q[e++] = i;
    }

    cout << dp[n-1] << endl;
}