Description：

有 $n$ 个牧场，在每个牧场建控制站有代价，每个控制站控制它左边控制站后面的所有牧场，每个牧场的代价是它到控制他的控制站的距离乘该牧场放养量，最小化总代价。

$1\le n\le 1000000$

Solution：

正着推很不好做，这道题有一个很好的思路，就是可以先求出一个好求的方案，再把更优的减掉。

如果只在 $n$ 建控制站的话，费用是 $\begin{align}\sum_{i=1}^nb[i]\times (n-i)\end{align}$ ，然后考虑在 $i$ 这个位置再建一个控制站能节省多少钱，设 $f[i]$ 表示后面都已经处理好，在 $i$ 这里建立控制站能节省的最大代价，转移为 $f[i]=\max(f[j]+sum[i]\times(j-i))-a[i]$ 。移个项就是 $f[j]=-sum[i]\times j+sum[i]\times i+a[i]+f[i]$ ， $-sum[i]$ 也就是斜率单调递增， $j$ 也就是位置单调递减，最大化截距也就是维护上凸壳。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

typedef long long ll;

ll a[MAXN],b[MAXN];

int q[MAXN],head = 1,tail = 0;

ll sum[MAXN];

ll f[MAXN];

double slope(int a,int b)

{

	return (double)(f[a] - f[b]) / (double)(a - b);

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%lld",&a[i]);

	for(int i = 1;i <= n;++i)scanf("%lld",&b[i]);

	for(int i = 1;i <= n;++i)sum[i] = sum[i - 1] + b[i];

	ll ans = 0;

	for(int i = 1;i <= n;++i)ans += (n - i) * b[i];

	ans += a[n];

	q[++tail] = n;

	for(int i = n - 1;i >= 1;--i)

	{

		while(head < tail && slope(q[head],q[head + 1]) < -sum[i])++head;

		f[i] = f[q[head]] + sum[i] * (q[head] - i) - a[i];

		while(head < tail && slope(q[tail],q[tail - 1]) > slope(q[tail],i))--tail;

		q[++tail] = i;

	}

	ll res = 0;

	for(int i = 1;i <= n;++i)res = max(res,f[i]);

	cout << ans - res << endl;

	return 0;

}