题目大意:
一行有 $n$ 个牧场,每个牧场建造控制站要 $a_i$ 的代价,若没有建控制站,则需要 $b_i\times 往右到最近的控制站的距离$ 的代价,问最小总代价。

解题思路:
我们设两个 $b_i$ 前缀和,方便计算一段牧场到某一控制站的代价:

$$S_i = \sum_{j=i}^n b_j$$

$$S'_i = \sum_{j=i}^n b_j\times(n-j+1)$$
于是不难想到$O(n^2)$的dp式子:

$$dp_i = min(dp_{j-1}+(S'_j-S'_{i})-(S_j-S_i)\times(n-i+1)+a_i)\ \ j\in[1,i]$$

然后转化一下,将下标 $i$ 与下标 $j$ 分开:

$$dp_i = min(dp_{j-1}+S'_j-S_j\times(n-i+1)-S'_{i}-S_i\times(n-i+1)+a_i)\ \ j\in[1,i]$$

$$dp_i = min(dp_{j-1}+[S'_j-S_j\times(n+1)+S_j\times i]-S'_{i}-S_i\times(n-i+1)+a_i)\ \ j\in[1,i]$$

$$dp_i = min(dp_j+S'_{j+1}-S_{j+1}\times(n-i+1))-S'_{i}-S_i\times(n-i+1)+a_i\ \ j\in[0,i-1]$$

若$k\le j\le i$,且决策 $j$ 比决策 $k$ 优:

$$dp_j+S'_{j+1}-S_{j+1}\times(n-i+1) \le dp_k+S'_{k+1}-S_{k+1}\times(n-i+1)$$

$$(dp_j+S'_{j+1})-(dp_k+S'_{k+1})\le (S_{j+1}-S_{k+1})\times(n-i+1)$$

$$令y_i = dp_i+S'_{i+1},\ x_i = S_{i+1}$$

原式变为斜率式:
$${{y_j-y_k}\over{x_j-x_k}} \le n-i+1$$

$$设k(j,k)={{y_j-y_k}\over{x_j-x_k}}$$

然后通过上述式子我们知道,$(n-i+1)$是随 $i$ 递增而递减的,而节点 $j$ 比节点 $k$ 优,当且仅当 $k(j,k)\le (n-i+1)$,若此时$k(j,k) > (n-i+1)$,那么随 $i$ 递增,节点 $j$ 将永不会比节点 $k$ 优,于是可以剔除这个节点。

同时,若 $k(i,j)>k(j,k), k<j<i$,那么节点 $j$ 将不会对答案做出贡献。
证明:
1.若 $k(j,k)k(i,j)<(n-i+1)$,那么节点 $j$ 比节点 $i$ 优,但是$k(j,k)<k(i,j)<(n-i+1)$,故节点 $k$ 比节点 $j$ 优。
2.若 $k(j,k)<(n-i+1)<k(i,j)$,那么节点 $i,k$ 都比节点 $j$ 优。
3.若 $k(i,j)\ge(n-i+1)$,那么节点 $i$ 比节点 $j$ 优。

知道这些后,我们可以用队列模拟一下将复杂度做到$O(n)$。

代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 1000005
using namespace std;
typedef long long LL;
inline LL read() {
    LL x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n;
static LL a[N], b[N], dp[N];
static LL S[N], Sc[N];
static int q[N], h, t;

void Input() {
    n = (int)read();
    for(int i=1; i<=n; i++) a[i] = read();
    for(int i=1; i<=n; i++) b[i] = read();
    
    S[n+1] = Sc[n+1] = 0;
    for(int i=n; i>=1; i--) S[i] = S[i+1] + b[i];
    for(int i=n; i>=1; i--) Sc[i] = Sc[i+1] + b[i] * (n-i+1);
}

inline LL getDP(int i, int j) { return dp[j]+(Sc[j+1]-Sc[i])-(S[j+1]-S[i])*(n-i+1)+a[i]; }
inline LL UP(int j, int k) { return (dp[j]+Sc[j+1])-(dp[k]+Sc[k+1]); }
inline LL DOWN(int j, int k) { return (S[j+1] - S[k+1]); }

void Solve() {
    for(int i=1; i<=n; i++) {
        while(h<t && UP(q[h+1],q[h])<=(n-i+1)*DOWN(q[h+1],q[h])) h++;
        dp[i] = getDP(i, q[h]);
        while(h<t && UP(i,q[t])*DOWN(q[t],q[t-1])>=UP(q[t],q[t-1])*DOWN(i,q[t])) t--;
        q[++t] = i;
    }
    printf("%lld\n", dp[n]);
}

int main() {
    Input();
    Solve();
    return 0;
}