题目描述
Description
小P在MC里有n个牧场，自西向东呈一字形排列（自西向东用1…n编号），于是他就烦恼了：为了控制这n个牧场，他需要在某些牧场上面建立控制站，每个牧场上只能建立一个控制站，每个控制站控制的牧场是它所在的牧场一直到它西边第一个控制站的所有牧场（它西边第一个控制站所在的牧场不被控制）（如果它西边不存在控制站，那么它控制西边所有的牧场），每个牧场被控制都需要一定的花费（毕竟在控制站到牧场间修建道路是需要资源的嘛~），而且该花费等于它到控制它的控制站之间的牧场数目（不包括自身，但包括控制站所在牧场）乘上该牧场的放养量，在第i个牧场建立控制站的花费是ai，每个牧场i的放养量是bi，理所当然，小P需要总花费最小，但是小P的智商有点不够用了，所以这个最小总花费就由你来算出啦。
Input
第一行一个整数 n 表示牧场数目
第二行包括n个整数，第i个整数表示ai
第三行包括n个整数，第i个整数表示bi
Output
只有一行，包括一个整数，表示最小花费
Sample Input
4
2424
3142
Sample Output
9
样例解释
选取牧场1，3，4建立控制站，最小费用为2+(2+1*1)+4=9。
1<=n<=1000000, 0 < a i ,bi < = 10000
题目分析
老样子 先列出方程
设f[i]为i建立控制站时前i个的最小代价。
那么有f[i]=f[j]+∑((i-k)*b[k])+a[i] (j+1≤k≤i)
=f[j]+∑(i*b[k])-∑(k*b[k])+a[i] (j+1≤k≤i)
=f[j]+i*(sum[i]-sum[j])-(t[i]-t[j])+a[i]
其中sum[i]为b[i]的前缀和，sumk[i]为b[i]*i的前缀和。
整理一下即为f[j]+sumk[j]=i*sum[j]+f[i]-i*sum[i]+sumk[i]-a[i]
之后斜率优化即可
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
long long a[2000000],b[2000000],sum[2000000],sumk[2000000],f[2000000];
int q[2000000],l,r;
long long yi(long long i) { return f[i]+sumk[i]; }
long long xi(long long i) { return sum[i]; }
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],sumk[i]=sumk[i-1]+b[i]*i;
for(long long i=1;i<=n;i++)
{
while(l<r&&yi(q[l+1])-yi(q[l])<i*(xi(q[l+1])-xi(q[l]))) l++;
f[i]=i*sum[i]-i*sum[q[l]]-sumk[i]+sumk[q[l]]+f[q[l]]+a[i];
while(l<r&&(yi(i)-yi(q[r]))*(xi(q[r])-xi(q[r-1]))<(yi(q[r])-yi(q[r-1]))*(xi(i)-xi(q[r]))) r--;
q[++r]=i;
}
printf("%lld",f[n]);
return 0;
}
/*f[i]=i*(sum[i]-sum[j])-(sumk[i]-sumk[j])+f[j]+a[i];
f[i]=i*sum[i]-i*sum[j]-sumk[i]+sumk[j]+f[j]+a[i];
f[i]-i*sum[i]+sumk[i]-a[i]+i*sum[j]=f[j]+sumk[j];*/
