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; }