[文章目录]
Description
小P在MC里有n个牧场，自西向东呈一字形排列（自西向东用1…n编号），于是他就烦恼了：为了控制这n个牧场，他需要在某些牧场上面建立控制站，每个牧场上只能建立一个控制站，每个控制站控制的牧场是它所在的牧场一直到它西边第一个控制站的所有牧场（它西边第一个控制站所在的牧场不被控制）（如果它西边不存在控制站，那么它控制西边所有的牧场），每个牧场被控制都需要一定的花费（毕竟在控制站到牧场间修建道路是需要资源的嘛~），而且该花费等于它到控制它的控制站之间的牧场数目（不包括自身，但包括控制站所在牧场）乘上该牧场的放养量，在第i个牧场建立控制站的花费是ai，每个牧场i的放养量是bi，理所当然，小P需要总花费最小，但是小P的智商有点不够用了，所以这个最小总花费就由你来算出啦。1<=n<=1000000, 0 < a i ,bi < = 10000
斜率优化。
朴素DP方程：设f[i]表示在i建控制站使得1~i都被控制的最小花费。f[i]=min(f[j]+(j+1~i所有点的花费))+a[i]。
发现j~i所有点的花费可以通过前缀和表示。设sw[i]为1~i-1到i的花费，s[i]为1~i的bi的和。那么方程可以表示为:f[i]=min(f[j]+sw[i]-sw[j]-i*s[j]+j*s[j])。发现i递增，s[j]递增。可以斜率优化。然后就是O(n)的了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,a[1001000],q[1001000];
ll s[1001000],sw[1001000],f[1001000];
ll b(int x){return f[x]-sw[x]+s[x]*x;}
ll k(int x){return -s[x];}
int main()
{
scanf("%d",&n); int i,x;
for(i=1;i<=n;++i) scanf("%d",a+i);
for(i=1;i<=n;++i)
{
scanf("%d",&x);
s[i]=s[i-1]+x;
sw[i]=sw[i-1]+s[i-1];
}
int h=1,t=1;
for(i=1;i<=n;++i)
{
while(h<t&&k(q[h])*i+b(q[h])>=k(q[h+1])*i+b(q[h+1])) h++;
f[i]=k(q[h])*i+b(q[h])+a[i]+sw[i];
while(h<t&&( b(q[t])-b(i) ) * ( k(q[t])-k(q[t-1]) ) <= ( b(q[t-1])-b(q[t]) ) * ( k(i)-k(q[t]) ) ) t--;
q[++t]=i;
}
printf("%lld\n",f[n]);
return 0;
}