闫氏dp分析法
斜率优化
代码
import java.io.*;
import java.util.*;
public class Main{
static int N = 3*100010;
static long[] c = new long[N],t = new long[N],f = new long[N];
static int[] q = new int[N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int s = sc.nextInt();
for(int i = 1;i<=n;i++){
t[i] = t[i-1]+sc.nextInt();
c[i] = c[i-1]+sc.nextInt();
}
int hh = 0,tt = 0;
//队列种有一个元素,斜率为0
for(int i = 1;i<=n;i++){
while(tt>hh&&
(f[q[hh+1]]-f[q[hh]])<=(s+t[i])*(c[q[hh+1]]-c[q[hh]])) hh++;
int j = q[hh];
f[i] = f[j]+s*(c[n]-c[j])+t[i]*(c[i]-c[j]);
while(tt>hh&&(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt]])
>=(f[i]-f[q[tt]])*(c[q[tt]]-c[q[tt-1]])) tt--;
q[++tt] = i;
}
System.out.println(f[n]);
}
}