【CSP2019】划分 | Mrsrz's blog

单调队列优化DP。

题目大意：

给定一个数列，要求将其划分为若干段。令第 $i$ 段的和为 $b_i$，划分成了 $k$ 段。

要求满足 $\forall i\in[2,n]$，$b_i\geq b_{i-1}$。

在此基础上最小化 $\sum\limits_{i=1}^k b^2_i$.

求最小值。

题解：

myy 的题解及证明

这玩意我不太会证啊

大概就是令最后一段尽可能小，令前一段尽可能小，依此类推。这样能使答案最优。感性理解吧

等我看懂了证明过程再来补。flag

这个东西的话，就是对每个位置，记录其最小的分段的位置。

这个可以用单调队列优化。

考虑位置 $i,j,k$ 满足 $ik$ 的每个 $p$，$[j,p]$ 也一定合法。此时位置 $i$ 就没用了。在单调队列中弹出队首。

考虑在队尾插入一个位置 $p$，队尾位置为 $i$，如果满足任意 $k>p$ 使 $[i,k]$ 合法的都能使 $[p,k]$ 合法，那么队尾元素也没有用了。弹出队尾即可。

这样保证每次决策时，队首都是最优的且后面的划分方案都不合法。

时间复杂度 $O(n)$。

这里只需记录每段的划分位置，最后计算答案。计算答案时需要用到高精度，用两个long long存即可。__int128在很多地方不能用，当做练习高精度好了。

注意前缀和一些奇奇怪怪的数组越界问题（

Code：

#include<iostream>
#include<cstdio>
using namespace std;
typedef unsigned long long LL;
const LL inf=1e18;
const int base=1e9;
const int N=4e7+3;
int n,type;
LL pre[N];
int sta[N],head,tail,lst[N];
inline LL sum(int l,int r){return pre[r]-pre[l-!!l];}
struct int128{
    LL a,b;
    inline int128 operator+(const int128&r)const{
        return(int128){a+r.a+(b+r.b>=inf),b+r.b-(b+r.b>=inf)*inf};
    }
}ans;
inline int128 sqr(LL x){
    int a=x/base,b=x%base;
    LL f=(LL)a*a+(LL)a*b*2/base,g=(LL)a*b*2%base*base+(LL)b*b;
    return(int128){f+g/inf,g%inf};
}
void get(){
    int x,y,z,m,ed=0;
    cin>>x>>y>>z>>pre[1]>>pre[2]>>m;
    for(register int i=3;i<=n;++i)
    pre[i]=(x*pre[i-1]+y*pre[i-2]+z)&1073741823;
    while(m--){
        int p,l,r;
        cin>>p>>l>>r;
        for(register int i=ed+1;i<=p;++i)
        pre[i]=pre[i-1]+(pre[i]%(r-l+1)+l);
        ed=p;
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>type;
    if(!type)
    for(int i=1;i<=n;++i)cin>>pre[i],pre[i]+=pre[i-1];
    else get();
    sta[head=tail=1]=0;
    for(register int i=1;i<=n;++i){
        while(head<tail&&sum(lst[sta[head+1]],sta[head+1])<=sum(sta[head+1]+1,i))
        ++head;
        lst[i]=sta[head]+1;
        const LL s=sum(lst[i],i);
        while(head<=tail&&sum(lst[sta[tail]],sta[tail])>=s+sum(sta[tail]+1,i))
        --tail;
        sta[++tail]=i;
    }
    for(int p=n;p;p=lst[p]-1)ans=ans+sqr(sum(lst[p],p));
    if(ans.a==0)printf("%llu\n",ans.b);else
    printf("%llu%018llu\n",ans.a,ans.b);
    return 0;
}