斜率优化

某次比赛中需要斜率优化发现写得极不顺畅。。。总结一个模板化的东西以后照抄。
SDOI2016 征途为例,题目要求的就是将n个数字的数组分成至多m段,使得每一段的和的平方的总和最小。

f[p][i]表示将前i个数字分成p段的和的最小值,转移显然。
斜率优化:对于一个点i,决策点k_1优于决策点k_2(k_1 < k_2 < i)

\begin{aligned}
f[p-1][k_1]+(s[i]-s[k_1])^2 & < f[p-1][k_2]+(s[i]-s[k_2])^2\\
\frac {(f[p-1][k_1]+s^2[k_1])-(f[p-1][k_2]+s^2[k_2])}{s[k_1]-s[k_2]} & > 2s[i]
\end{aligned}

也就是,当上面的不等式中间为\le时,k_1就可以被扔掉,扔掉之后,队首两个元素的斜率应该上升,直到 > 2s[i]
因此按照这个式子,由于s[i]是不下降的,所以维护决策点连线斜率单增的队列,也就是决策点构成的下凸壳,然后维护下凸壳可以用计算几何的方法。。。
如果某个a[i]=0,那么s[i]=s[i-1],也就是ii-1决策点的横坐标相同,那么i点的纵坐标必定\le i-1点的纵坐标。如果纵坐标相等,要注意去掉这个重复点,否则,放在维护下凸壳的算法里,这种情形也能正确处理。

const int XN=3000+11;

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    static int a[XN],f[XN][XN],sum[XN];
    int n,m;std::cin>>n>>m;
    for(int i=1;i<=n;++i) {
        std::cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        f[1][i]=sum[i]*sum[i];
    }
    for(int p=2;p<=m;++p) {
        static int Q[XN],head,tail;

        Q[head=0]=p-1;tail=1;
        for(int i=p;i<=n;++i) {
            auto Calc=[&](int t)->int {
                return f[p-1][t]+(sum[i]-sum[t])*(sum[i]-sum[t]);
            };

            auto TurnRight=[&](std::array<int,3> id)->bool {
                std::array<long long,3> x,y;
                for(int i=0;i<3;++i) {
                    x[i]=sum[id[i]];
                    y[i]=f[p-1][id[i]]+sum[id[i]]*sum[id[i]];
                }
                return (x[1]-x[0])*(y[2]-y[1])-(x[2]-x[1])*(y[1]-y[0])<=0;
            };

            while(tail-head>=2 && Calc(Q[head])>=Calc(Q[head+1]))
                head++; 

            f[p][i]=Calc(Q[head]);

            while(tail-head>=2 && TurnRight({Q[tail-2],Q[tail-1],i}))
                tail--;
            Q[tail++]=i;
        }
    }
    int Ans=f[m][n]*m-sum[n]*sum[n];
    std::cout<<Ans<<'\n';
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注