Codeforces Round #189 (Div. 1) C. Kalila and Dimna in the Logging Industry

問題ページ Problem - C - Codeforces

解法

n本目の木を切ったあとはチャージし放題なのでコスト0で全ての木を切れる。したがってn本目の木を切るのに必要なコストを求めればよい。また、j本目の木を切った後にj本目より前の木を切ったとしてもチャージに使う木はjから変わらないので得することはない。
dp[i] = (i本目の木を切るのにかかるコスト) とすると漸化式は
dp[i] = min(dp[j]+b[j]*a[i] | j<i), dp[0] = 0
となる。このまま愚直に計算するとO(N^2)でTLEだが傾きb[j]、切片dp[j]の直線群に対するconvexHullTrickとして解くことでO(N)で求めることができる。
注意点としてCHTでいらない直線かどうかの判断をする部分(下の実装ではcheck())でよくある書き方をしていると積の結果が64bitに収まらず落ちるパターンがある。別に一回落ちてもいいので誤差死を気にせず多分通るだろうと思いlong doubleで投げたら通ったけどフルフィードバックでない本番だったら多分多倍長整数を使ってると思う。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

// 直線の傾きに単調性があるときのCHT O(n)
// 最大なら <= になる
class ConvexHullTrick {
public:
  deque<PII> que;
  // ax + b を追加
  void add(int a, int b) {
    PII p(a, b);
    while(que.size() >= 2 && check(que[que.size()-2], que.back(), p)) {
      que.pop_back();
    }
    que.push_back(p);
  }
  // 単調性がある xの位置での最小のy
  int incl_query(int x) {
    assert(que.size());
    while(que.size() >= 2 && f(que[0],x) >= f(que[1],x)) {
      que.pop_front();
    }
    return f(que[0],x);
  }
  // 単調性なし
  int query(int x) {
    int lb = -1, ub = que.size()-1;
    while(ub-lb > 1) {
      int mid = (lb+ub)/2;
      if(isright(que[mid], que[mid+1], x)) lb = mid;
      else ub = mid;
    }
    return f(que[ub], x);
  }

  bool isright(const PII &p1, const PII &p2, int x) {
    return (p1.second-p2.second) >= x * (p2.first-p1.first);
  }
  bool check(const PII &a, const PII &b, const PII &c) {
    return (long double)(b.first-a.first)/(b.second-a.second)>=(long double)(c.first-b.first)/(c.second-b.second);
  }
  int f(const PII &p, int x) {
    return p.first * x + p.second;
  }
};
ConvexHullTrick cht;

int a[100010], b[100010], dp[100010];
signed main(void)
{
  int n;
  cin >> n;
  REP(i, n) cin >> a[i];
  REP(i, n) cin >> b[i];

  dp[0] = 0;
  cht.add(b[0], dp[0]);
  FOR(i, 1, n) {
    dp[i] = cht.query(a[i]);
    cht.add(b[i], dp[i]);
  }
  cout << dp[n-1] << endl;

  return 0;
}