我一般采用的方法是 截距式优化。
更快速 更正轨的是采用代数法进行斜率优化 这种方法 使用较多且使用范围广泛。
注意：斜率优化和决策单调性 含义不相同 决策单调性一般是四边形不等式优化出来的结果。
而斜率优化只是在解决一些特定问题寻找最优决策时的优化。
通常题目可能可以同时进行斜率优化或决策单调性优化 但决策单调性优化有下界复杂度Qlog 而斜率优化如果斜率单调通常可以使O(Q)的。
LINK：CF631E Product Sum
对于一个数列我们定义其代价为 (sum_{i=1}{n}icdot a_i)
可以将某个i交换到j 使得j之后的数字往后推形成的新的序列最大。
显然我们可以(n^2)暴力之后O(1)算出贡献。但是这不够优秀。
i可以向前也可以向后 我们先考虑向前的方向。显然设f[i]表示i和1~i这些位置中的一个交换得到的最大价值。
设原本的初始值为m.那么f[i]可以表示 换过后的值和初始值的差。
(f_i=(j-i)cdot a_i+sum_{i-1}-sum_{j-1})
这个时候一般是要对比一下两个决策 再来一个决策k (1leq k<j)
(f_i=(k-i)cdot a_i+sum_{i-1}-sum_{k-1})
我们可以让他们来一个 大小关系的比较看能得出什么 假设j决策优于k决策。
显然有 ((j-i)cdot a_i+sum_{i-1}-sum_{j-1}geq (k-i)cdot a_i+sum_{i-1}-sum_{k-1})
化简一下 ((j-k)cdot a_igeq sum_{j-1}-sum_{k-1} o a_igeq frac{sum_{j-1}-sum_{k-1}}{j-k})
到这里 可以发现右边 神似我们的斜率式子 也就是 在一个二维坐标系中我们以w为下标 (sum_{w-1})为总坐标
右边其实是我们坐标系中的一个两点的斜率 也同样说明了 如果我们的(a_i)大于这个斜率说明了j是比k优的的。
此时 如果只有一个斜率没的说比一下即可 有三个点的时候 我们可以来分析一下他们之间的关系 我分析的话过于抽象 可以自己分析 j1,j2,j3看一下他们有什么关系。
可以发现上凸包一定不优策略 我们删掉一些点形成下凸 斜率单调递增。
接下来直接在凸包上线性规划即可 由于这道题 ai不单调 所以需要在凸包上二分。
反着的过程也同样如此。
其实 代数法优化的优越性 这道题没体现出来 但是简洁性还是很棒的。
const ll MAXN=200010;
ll n,w,l,r,cnt;
ll a[MAXN],f[MAXN],sum[MAXN];
ll q[MAXN];
inline db slope(ll x,ll y){return 1.0*(sum[y-1]-sum[x-1])/(y-x);}
inline db slope1(ll x,ll y){return 1.0*(sum[y]-sum[x])/(y-x);}
inline ll find(ll x)
{
if(r==1)return q[l];
ll L=1,R=r;
while(L+1<R)
{
ll mid=(L+R)>>1;
if(slope(q[mid-1],q[mid])>=x)R=mid;
else L=mid;
}
if(slope(q[L],q[R])>=x)return q[L];
return q[R];
}
inline ll find2(ll x)
{
if(r==1)return q[l];
ll L=1,R=r;
while(L+1<R)
{
ll mid=(L+R)>>1;
if(slope1(q[mid-1],q[mid])>=x)L=mid;
else R=mid;
}
if(slope1(q[L],q[R])>=x)return q[R];
return q[L];
}
int main()
{
freopen("1.in","r",stdin);
get(n);
rep(1,n,i)get(a[i]),w+=a[i]*i,sum[i]=sum[i-1]+a[i];
q[l=r=1]=1;
rep(2,n,i)
{
ll w=find(a[i]);//二分凸包
f[i]=(w-i)*a[i]+sum[i-1]-sum[w-1];
while(l<r&&slope(q[r],i)<=slope(q[r-1],q[r]))--r;
q[++r]=i;cnt=max(cnt,f[i]);
}
//f[i]= (j-i)*ai-sum[j]+sum[i];
q[l=r=1]=n;
for(ll i=n-1;i>=1;--i)
{
ll w=find2(a[i]);
f[i]=(w-i)*a[i]-sum[w]+sum[i];
while(l<r&&slope1(q[r],i)>=slope1(q[r-1],q[r]))--r;
q[++r]=i;cnt=max(cnt,f[i]);
}
printf("%lld
",cnt+w);
return 0;
}
这道题并不算简单 反着的时候很容易迷 建议反着的时候画画图再写。
记得我上次写反着的时候是再模拟赛上CDQ分治套斜率优化 迷死我了 然后写+调了快3h 结果崩盘了