bzoj 3437 小p的农场

思路

\(f[i]=min(f[j]+\sum\limits_{k=j+1}^{i}{b[k]*(i-k)}+a[i])\)
\(f[i]=min(f[j]+\sum\limits_{k=j+1}^{i}{(b[k]*i-b[k]*k)}+a[i])\)
再来前缀和处理一下就可以做到\(O(n^2)\)
\(f[i]=min(f[j]+(sum[i]-sum[j])*i-(sum\_k[i]-sum\_k[j])+a[i])\)
然后斜率优化加速
ps:斜率优化好多前缀和，都单调
\(f[i]=min(-sum[j]*i+sum[i]*i-sum\_k[i]+sum\_k[j]+a[i]+f[j])\)
\((-sum[j]*i+sum\_k[j]+f[j]) < (-sum[j]*i+sum\_k[j]+f[j])\)
\(sum\_k[j]-sum\_k[k]+f[j]-f[k] < (sum[j]-sum[k])*i\)
\(\frac{sum\_k[j]-sum\_k[k]+f[j]-f[k]}{(sum[j]-sum[k])} < i\)

错误原因

b[i]*i爆掉了，真的还是那句话，无处不炸longlong，气死啦
不过斜率优化真的模板哇

代码

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int N=1e6+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,q[N],a[N],b[N];
ll sum[N],sum_k[N],f[N];
double calc(int j,int k) {
    return (double)(sum_k[j]-sum_k[k]+f[j]-f[k])/(double)(sum[j]-sum[k]);
}
int main() {
    n=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=n;++i) {
        b[i]=read();
        sum[i]=sum[i-1]+b[i];
        sum_k[i]=sum_k[i-1]+(ll)b[i]*i;
    }
    /*
    //@baoli
    f[0]=0;
    for(int i=1;i<=n;++i) {
        f[i]=inf;
        for(int j=0;j<i;++j)
            f[i]=min(f[i],f[j]+(sum[i]-sum[j])*i-(sum_k[i]-sum_k[j])+a[i]);
    }
    */
    int h=1,d=1;
    for(int i=1;i<=n;++i) {
        while(h<d && calc(q[h],q[h+1]) < i) h++;
        f[i]=f[q[h]]+(sum[i]-sum[q[h]])*i-(sum_k[i]-sum_k[q[h]])+a[i];
        while(h<d && calc(q[d],q[d-1]) >= calc(q[d],i)) d--;
        q[++d]=i;
    }
    cout<<f[n]<<"\n";
    return 0;
}