末尾が楽曲 \(i\) であるプレイリストの総合スコアの最大値を \(\mathrm{dp}[i]\) とします。

末尾が楽曲 \(j\) で総合スコアが \(S\) であるプレイリストの末尾に楽曲 \(i\) を追加すると、そのプレイリストの総合スコアは \(S+A_i+B_jB_i\) となります。

よって、末尾が楽曲 \(i\) であるプレイリストの総合スコアの最大値は、\(i\) の前の楽曲が何であるかを考えることで

\(\begin{aligned} \mathrm{dp}[i] &=\max(A_i, \max_{j<i}(\mathrm{dp}[j]+A_i+B_jB_i))\\ &=A_i+\max(0, \max_{j<i}(\mathrm{dp}[j]+B_jB_i)) \end{aligned}\)

となります。ここで max を取る対象は、\(\mathrm{dp}[j]+B_jx\) という 1 次式の \(x=B_i\) のときの値であり、\(i\) の昇順にこのDPを行うとき、max を取る対象となる1次式の集合は単調に増大することから、CHT(convex hull trick)を用いて高速化することができ、 \(O(N\log N)\) でこの問題を解くことができます。

CHT

CHTとは、次のような、直線群に対する操作を行うクエリを、クエリあたり \(O(\log N)\) で処理するアルゴリズムのことです。

• 直線 \(L\) が与えられる。直線の集合 \(S\) に \(L\) を追加する
• 値 \(t\) が与えられる。直線の集合 \(S\) に属する直線たちの \(x=t\) での値の最大値を求める。

このアルゴリズムは、クエリで与えられる \(t\) が事前にわかっている場合には、セグメントツリーを模した二分木のデータ構造である Li Chao Tree を用いて実現することができます。

実装例

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

struct LiChaoTree{
  struct Line{
    ll a, b;
    Line(ll a, ll b): a(a), b(b){}
    ll eval(ll x){return a * x + b;}
  };

  int n;
  vector<ll> xs;
  vector<Line> seg;
  
  LiChaoTree(vector<ll> xs): xs(xs){
    n = xs.size();
    seg = vector<Line>(4 * n, Line(0, -1e18));
  }

  void add(ll a, ll b){
    Line line = Line(a, b);
    int i = 1, l = 0, r = n;

    while(r - l > 1){
      int m = (l + r) / 2;
      bool left = line.eval(xs[l]) > seg[i].eval(xs[l]);
      bool mid  = line.eval(xs[m]) > seg[i].eval(xs[m]);

      // midで強い方をこのノードに残す
      if(mid){
        swap(line, seg[i]);
      }
    
      //left, mid間で交差してるなら左にいく、そうでないなら右
      i *= 2;
      if(left != mid) r = m;
      else l = m, i++;
    }
    
    // 葉
    if(line.eval(xs[l]) > seg[i].eval(xs[l])){
      swap(line, seg[i]);
    }
  }
  
  ll query(ll x){
    int i = 1, l = 0, r = n;
    ll ans = seg[i].eval(x);

    while(r - l > 1){
      int m = (l + r) / 2;
      i *= 2;
      if(x < xs[m]) r = m;
      else l = m, i++;
      ans = max(ans, seg[i].eval(x));
    }
    return ans;
  }
};

int main(){
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for(int i=0; i<n; i++) cin >> a[i] >> b[i];

  set<int> s(b.begin(),b.end());
  vector<ll> bi(s.begin(),s.end());
  auto seg = LiChaoTree(bi);

  vector<ll> dp(n);
  dp[0] = a[0];
  seg.add(b[0], dp[0]);
  for(int i=1; i<n; i++){
    dp[i] = a[i] + max(0LL, seg.query(b[i]));
    seg.add(b[i], dp[i]);
  }

  cout << *max_element(dp.begin(), dp.end()) << endl;
}

実装例 (Python)

class LiChaoTree:
  class Line:
    def __init__(self, a, b):
      self.a = a
      self.b = b
    def eval(self, x):
      return self.a * x + self.b

  def __init__(self, xs):
    self.xs = xs
    self.n = len(xs)
    self.seg = [self.Line(0, -10**18) for _ in range(4 * self.n)]
  
  def add(self, a, b):
    line = self.Line(a, b)
    i = 1
    l, r = 0, self.n

    while r - l > 1:
      m = (l + r) // 2
      left = line.eval(self.xs[l]) > self.seg[i].eval(self.xs[l])
      mid  = line.eval(self.xs[m]) > self.seg[i].eval(self.xs[m])
      
      # mid で強い方をこのノードに残す
      if mid:
        line, self.seg[i] = self.seg[i], line
      
      # left, mid間で交差しているなら左に行く、そうでないなら右
      if left != mid:
        r = m
        i = 2 * i
      else:
        l = m
        i = 2 * i + 1

    # 葉
    if line.eval(self.xs[l]) > self.seg[i].eval(self.xs[l]):
      line, self.seg[i] = self.seg[i], line
  
  def query(self, x):
    i = 1
    l, r = 0, self.n
    ans = self.seg[i].eval(x)
    
    while r - l > 1:
      m = (l + r) // 2
      if x < self.xs[m]:
        r = m
        i = 2 * i
      else:
        l = m
        i = 2 * i + 1
      ans = max(ans, self.seg[i].eval(x))

    return ans

N = int(input())
AB = [tuple(map(int,input().split())) for _ in range(N)]

bi = sorted(set(b for _, b in AB))
seg = LiChaoTree(bi)

dp = [0] * N
a, b = AB[0]
dp[0] = a
seg.add(b, dp[0])

for i in range(1, N):
  a, b = AB[i]
  dp[i] = a + max(0, seg.query(b))
  seg.add(b, dp[i])

print(max(dp))