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;
}