【BZOJ3437】小P的牧场（动态规划，斜率优化）

题面

题解

考虑暴力(dp)，设(f[i])表示强制在(i)处建立控制站的并控制([1..i])的最小代价。
很显然，枚举上一个控制站的位置(j)
(f[i]=min(f[j]+Calc(i,j)+a[i]))，其中(Calc(i,j))表示(i,j)之间被(i)控制的位置产生的贡献。
这个可以用前缀和优化做到(O(1))计算(Calc)
预处理(s1[i]=sum b[i],s2[i]=sum (n-i+1)*b[i])
那么(Calc(i,j)=s2[i]-s2[j]-(s1[i]-s1[j])*(n-i+1))
考虑两个位置(j,k)，满足(klt j)，并且(k)的转移劣于(j)
那么
(f[k]+Calc(i,k)gt f[j]+Calc(i,j))
拆开之后是：
(f[k]-s2[k]+s1[k]*(n-i+1)gt f[j]-s2[j]+s1[j]*(n-i+1))
令(g[i]=f[i]-s2[i]+s1[i]*(n+1))
将所有项按照是否与(i)相关分类，可以得到
((g[k]-g[j])gt (s1[k]-s1[j])*i)
因为(k<j)，所以(s1[k]<s1[j])，除过去要变号

[i>frac{g[k]-g[j]}{s1[k]-s1[j]} ]

妥妥的斜率优化，因为(i)单增，可以单调队列解决。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define RG register
#define MAX 1000100
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int n,a[MAX],b[MAX];
int Q[MAX],h,t;
ll f[MAX],s1[MAX],s2[MAX];
ll calc(int i,int j){return f[j]+s2[i]-s2[j]-(s1[i]-s1[j])*(n-i+1)+a[i];}
double Slope(int j,int k)
{
	double gj=f[j]-s2[j]+1.0*s1[j]*(n+1);
	double gk=f[k]-s2[k]+1.0*s1[k]*(n+1);
	return 1.0*(gj-gk)/(s1[j]-s1[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();
	for(int i=1;i<=n;++i)s1[i]=s1[i-1]+b[i];
	for(int i=1;i<=n;++i)s2[i]=s2[i-1]+1ll*(n-i+1)*b[i];
	Q[h=t=1]=0;
	for(int i=1;i<=n;++i)
	{
		while(h<t&&Slope(Q[h],Q[h+1])<=i)++h;
		int j=Q[h];f[i]=calc(i,j);
		while(h<t&&Slope(Q[t],Q[t-1])>=Slope(Q[t-1],i))--t;
		Q[++t]=i;
	}
	printf("%lld
",f[n]);
}