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

Problem - C - Codeforces

題意：
有 N 棵樹，用長度 A[ i ] 和魔力 B[ i ] 描述。保證 A 嚴格遞減，B 嚴格遞增，且 A[ 0 ] = 1, B[ N - 1 ] = 0。一次操作選擇一顆長度不為 0 的樹，使之長度少一。每操作完後，必須選擇一棵長度已為 0 的樹的魔力，加到總花費上，才能進行下一次操作。求把所有樹的長度變為 1 需要最少多少總花費。

資料規模：
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

解法：
因為最後一棵樹砍倒後，接續的所有花費都為 0，因此問題轉換為砍倒最後一棵樹需要的最少總花費。考慮動態規劃：
dp[ i ]：已砍倒第 i 棵樹，此時最少總花費
dp[ i ] = 0, if i = 0
________= min{ dp[ j ] + B[ j ] * A[ i ], for each 0 ≤ j < i }, otherwise
很明顯是斜率優化 DP，用經典凸包加速，又因為保證斜率嚴格遞減，所以實在是很經典。

時間 / 空間複雜度：
O( N )

注意：
第 27 行，long long int 會溢位，因此用浮點比較。

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