首页 > itarticle > cf

cf

admin 11月 14, 2020 0

Array Splitting

题意

将一个长度为 $n$ 的序列 $a_i$ 顺序不变的分为非空的 $k$ 部分, 设 $f(i)$ 表示 $a_i$ 在第 $f(i)$ 部分

求 $sumlimits_{i=1}^na_i*f(i)$

题解

在 $[1,n]$ 中选 $k$ 个点 $b_i$ (其中一个为 1)将序列分为 $k$ 份, 答案为 $sumlimits_{i=1}^ksuf[i]$ , $suf[i]$ 表示从 $i$ 开始的后缀和

所以直接对后缀排序, 取最大的 $k$ 个

代码

int a[N];
ll suf[N];
bool (ll x,ll y){
    return x>y;
}
int main() {
    int n,k;
    in(n,k);
    for0(i,n)in(a[i]);
    for(itn i=n-1;i>=0;i--){
        suf[i]=suf[i+1]+a[i];
    }
    sort(suf+1,suf+n,cmp);
    ll ans=0;
    for0(i,k){
        ans+=suf[i];
    }
    outln(ans);
    return 0;
}