UOJ104 [APIO2014] Split the sequence [斜率优化]

Solution

通过观察可得,如果已经规定了分割方案,则分割顺序不影响分割得到的结果。

考虑被分成的数个块。当一个块与另一个块被分割开来,整个式子中就出现两个块相乘的项,并且只会出现一次。

所以假设被分成了四个块$s_1,s_2,s_3,s_4$,那么结果就是$s_1s_2+s_1s_3+s_1s_4+s_2s_3+s_2s_4+s_3s_4$。

然后就可以分$k$层斜率优化了。

注意细节,一是$x$不一定是严格递增的,二是一定至少要分割$k$次。

不建议在luogu测,luogu数据太水了。

Code

// Code by ajcxsu
// Problem: sequence div

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
typedef long long ll;
ll f[2][N], *tf=f[0], *lf=f[1], x[N], y[N], s[N];
int pre[201][N];
int qu[N], h, t;

int main() {
    int n, k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>s[i], s[i]+=s[i-1];
    ll K; int j; 
    for(int nk=1;nk<=k;nk++) {
        swap(tf, lf);
        h=t=0;
        for(int i=nk;i<=n;i++) {
            K=-s[i];
            while(t-h>1 && y[qu[h+1]]-y[qu[h]]>(x[qu[h+1]]-x[qu[h]])*K) h++;
            if(t!=h) j=qu[h], tf[i]=y[j]-K*x[j], pre[nk][i]=j;
            x[i]=s[i], y[i]=lf[i]-s[i]*s[i];
            while((t-h>1 && (y[qu[t-1]]-y[qu[t-2]])*(x[i]-x[qu[t-1]])<(y[i]-y[qu[t-1]])*(x[qu[t-1]]-x[qu[t-2]]))
                        || (t-h && x[i]==x[qu[t-1]] && y[i]>=y[qu[t-1]])) t--;
            qu[t++]=i;
        }
    }
    cout<<tf[n]<<endl;
    for(int i=k, na=pre[k][n];i>=1;i--, na=pre[i][na]) cout<<na<<' ';
    cout<<endl;
    return 0;
}

本文链接:https://acxblog.site/archives/sol-uoj-104.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。