题意：
n个牧场，在每个牧场见控制站的花费为ai，在该处建控制站能控制从此处到左边第一个控制站（或边界）之间的牧场。一个牧场被控制的花费等于它到控制它的控制站之间的牧场数目（不包括自身，但包括控制站所在牧场）乘上该牧场的放养量。求最小费用。
题解：
推公式：
f[i]=f[j]+sigma(k,j+1,i)((i-k)*b[k])+a[i]
=f[j]+sigma(k,j+1,i)(i*b[k]-k*b[k])+a[i]
=f[j]+sigma(k,j+1,i)(i*b[k])-sigma(k,j+1,i)(k*b[k])+a[i]
=f[j]+i*sigma(k,j+1,i)b[k]-sigma(k,j+1,i)(k*b[k])+a[i]
sigma(k,j+1,i)b[k]和sigma(k,j+1,i)k*b[k]可用前缀和维护，故原式=f[j]+i*(sum1[i]-sum1[j])-(sum2[i]-sum2[j])+a[i]，然后就可以斜率优化了：
f[j]+i*(sum1[i]-sum1[j])-(sum2[i]-sum2[j])+a[i]<f[k]+i*(sum1[i]-sum1[k])-(sum2[i]-sum2[k])+a[i]
等价于f[j]-i*sum1[j]+sum2[j]<f[k]-i*sum1[k]+sum2[k]等价于f[j]-f[k]+sum2[j]-sum2[k]<i*(sum1[j]-sum1[k])，当j<k时满足
(f[j]-f[k]+sum2[j]-sum2[k])/(sum1[j]-sum1[k])>i。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1000010
#define ll long long
using namespace std; inline ll read(){
char ch=getchar(); ll f=,x=;
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return f*x;
}
ll f[maxn],sm1[maxn],sm2[maxn],a[maxn]; int n,q[maxn],l,r;
inline double calc(int j,int k){
return ((double)f[j]-f[k]+sm2[j]-sm2[k])/((double)sm1[j]-sm1[k]);
}
int main(){
n=read(); inc(i,,n)a[i]=read();
inc(i,,n){ll b=read(); sm1[i]=sm1[i-]+b; sm2[i]=sm2[i-]+b*i;} l=r=; q[l]=;
inc(i,,n){
while(l<r&&calc(q[l],q[l+])<i)l++; f[i]=f[q[l]]+i*(sm1[i]-sm1[q[l]])-sm2[i]+sm2[q[l]]+a[i];
while(l<r&&calc(q[r-],q[r])>calc(q[r],i))r--; q[++r]=i;
}
printf("%lld",f[n]); return ;
}
20160811