2018.10.23-dtoj-1751小P的牧场(pasture)

题目描述：

小P是个特么喜欢玩MC 的孩纸。。。
小P在MC 里有n 个牧场，自西向东呈一字形排列(自西向东用1...n 编号)，于是他就烦恼了：为了控制这n 个牧场，他需要在某些牧场上面建立控制站，每个牧场上只能建立一个控制站，每个控制站控制的牧场是它所在的牧场一直到它西边第一个控制站的所有牧场(它西边第一个控制站所在的牧场不被控制)(如果它西边不存在控制站，那么它控制西边所有的牧场)，每个牧场被控制都需要一定的花费(毕竟在控制站到牧场间修建道路是需要资源的嘛~)，而且该花费等于它到控制它的控制站之间的牧场数目(不包括自身，但包括控制站所在牧场)乘上该牧场的放养量，在第i 个牧场建立控制站的花费是ai，每个牧场i 的放养量是bi，理所当然，小P需要总花费最小，但是小P的智商有点不够用了，所以这个最小总花费就由你来算出啦。

输入：

第一行一个整数n 表示牧场数目
第二行包括n个整数，第i个整数表示ai
第三行包括n个整数，第i个整数表示bi

输出：

只有一行，包括一个整数，表示最小花费

数据范围：

对于10%的数据，1 <= n <= 10
对于30%的数据，1 <= n <= 1000
对于100%的数据，1 <= n <= 1000000 , 0 < ai,bi <= 10000

算法标签：斜率优化

思路：

其实是一道比较裸的斜率优化，一开始我为什么sb列了个二维式子，绝对的自己推式子能力爆弱，化对式子就是很明了的斜率优化了。

式子：s[i]前缀和，c[i]=∑a[j]*j ，f[i]=f[j]+(sum[i]-sum[j])*i-c[i]+c[j]+a[i]; (i,j上面是否要加一减一这类的要注意1下下)

以下代码：

#include<bits/stdc++.h>
#define il inline
#define LL long long
#define D double
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
const int N=1e6+5;int n,a[N],b[N],q[N],l=1,r=1;LL f[N],s[N],c[N];
il int read(){int x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return f*x;}
il LL Y(int a){return f[a]+c[a];}
il LL X(int a){return s[a];}
il D K(int a,int b){return (D)(Y(b)-Y(a))/(D)(X(b)-X(a));}
int main()
{
    n=read();for(int i=1;i<=n;i++)a[i]=read();for(int i=1;i<=n;i++)b[i]=read();
    for(int i=1;i<=n;i++)s[i]=s[i-1]+(LL)b[i],c[i]=c[i-1]+(LL)b[i]*(LL)i;
    for(int i=1;i<=n;i++){
        while(l<r&&K(q[l],q[l+1])<(D)i)l++;
        int j=q[l];
        f[i]=f[j]+(s[i]-s[j])*(LL)i+c[j]-c[i]+(LL)a[i];
        while(l<=r&&K(q[r-1],q[r])>K(q[r],i))r--;
        q[++r]=i;
    }
    printf("%lld
",f[n]);
  return 0;
}