読者です 読者をやめる 読者になる 読者になる

Codeforces #189 Div1. C Kalila and Dimna in the Logging Industry

Convex-Hull Trickを蟻本の形のまま使える問題があったのでメモ。

b[n-1] = 0に気付けると、
dp[0] = 0,
dp[i] = min[j=0, i - 1] (dp[j] + b[j] * a[i]) (i >= 1)
とすればO(N^2)で計算出来ることがわかる。
y = b[j] * x + dp[j]のa[i]での値であって、b[j] : 単調減少, a[i] : 単調増加より蟻本のまま適用できる。

直線の上下判定に超苦戦(long longをあふれるのに気付かなかった。)

#include <algorithm>
#include <cstdio>
using namespace std;

typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)

int n;
ll a[100010], b[100010];
ll dp[100010];
int deq[100010];
int s, t;

ll f(int j, int pos){
    return b[j] * a[pos] + dp[j]; 
}

bool ng(int t1, int t2, int t3){
    double a1 = b[t1], b1 = dp[t1];
    double a2 = b[t2], b2 = dp[t2];
    double a3 = b[t3], b3 = dp[t3];
    return (a2 - a1) * (b3 - b2) >= (b2 - b1) * (a3 - a2);
}

int main(){
    scanf("%d", &n);
    rep(i, n) scanf("%I64d", &a[i]);
    rep(i, n) scanf("%I64d", &b[i]);

    for(int i = 1; i < n; ++i){
	while(s + 1 < t && ng(deq[t - 2], deq[t - 1], i - 1)) --t;
	deq[t++] = i - 1;

	while(s + 1 < t && f(deq[s], i) >= f(deq[s + 1], i)) ++s;
	dp[i] = f(deq[s], i);
    }
    printf("%I64d\n", dp[n-1]);

    return 0;
}