# CFR 319 C. Kalila and Dimna in the Logging Industry ( DP, Convex Hull Trick )

Problem - C - Codeforces

The first line of input contains an integer n (1 ≤ n ≤ 1e5). The second line of input contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1e9). The third line of input contains n integers b1, b2, ..., bn (0 ≤ bi ≤ 109).
It's guaranteed that a1 = 1, bn = 0, a1 < a2 < ... < an and b1 > b2 > ... > bn.
TL: 2000 ms
ML: 256 MB

dp[ i ]：已砍倒第 i 棵樹，此時最少總花費
dp[ i ] = 0, if i = 0
________= min{ dp[ j ] + B[ j ] * A[ i ], for each 0 ≤ j < i }, otherwise

O( N )

check 函數的部分必須維護，如上圖，當插入的直線前面那一個永遠都沒有機會有用，就要 pop 掉。如果不退出的話，注意到 ( L3, L1 ) 的交點的 x 座標和 ( L2, L1 ) 的交點的 x 座標間，因為 L1 只會和 L2 比較，所以會沒有辦法發現其實有更優的 L3。因此插入新的線 L3 前，pop 掉隊尾的條件為，( L1, L2 ) 的交點下存在 L3 的某個點。

int N;
vi A;
vi B;

void init(){
cin >> N;
A = vi( N );
for( int i = 0; i < N; ++i ){
cin >> A[ i ];
}
B = vi( N );
for( int i = 0; i < N; ++i ){
cin >> B[ i ];
}
}

struct line{
ll slope, inter;
line( ll _s, ll _i ): slope( _s ), inter( _i ){}
ll operator () ( ll x ){ return x * slope + inter; }
};

int check( line f1, line f2, line f3 ){
ll a1 = f1.slope, b1 = f1.inter;
ll a2 = f2.slope, b2 = f2.inter;
ll a3 = f3.slope, b3 = f3.inter;
double x = -1.0 * ( b1 - b2 ) / ( a1 - a2 );
double y = x * a1 + b1;
return x * a3 + b3 <= y;
}

vl dp;

void preprocess(){
dp = vl( N );
deque< line > dq;
dq.emplace_back( line( B[ 0 ], dp[ 0 ] = 0 ) );
for( int i = 1; i < N; ++i ){
while( dq.size() >= 2 and dq[ 0 ]( A[ i ] ) >= dq[ 1 ]( A[ i ] ) ){
dq.pop_front();
}
dp[ i ] = dq[ 0 ]( A[ i ] );
line newl( B[ i ], dp[ i ] );
while( dq.size() >= 2 and check( dq[ dq.size() - 2 ], dq[ dq.size() - 1 ], newl ) ){
dq.pop_back();
}
dq.emplace_back( newl );
}
}

void solve(){
cout << dp[ N - 1 ] << endl;
}