题解：P5665 [CSP-S2019] 划分

· · 题解

首先对于两个段 a 与 b，且 a<b，显然 (a+b)^2>a^2+b^2。

于是需要在 a<b 的情况尽量多分段，于是考虑 dp。

设 dp_i 为前 i 个数的最优运行时间。

因为多分段，所以 dp_i 的最后一段一定最小，所以 dp_i 对于后买你的状态一定最优。

我们将 dp_i 的最后一段和记为 l_i。

设 dp_i 是从 dp_j 转移来的，那么 l_i=\sum_{k=j+1}^ia_k。

得出代码。

#include<bits/stdc++.h>
using namespace std;
int n,FW_number;
int a[100010];
__int128 s[100010];
__int128 dp[5010];
inline void write(__int128 x){
    if(x<0){
        putchar('-');
        write(-x);
        return;
    }
    if(x<10){
        putchar(x%10+'0');
        return;
    }
    write(x/10);
    putchar((x%10)^48);
}
int l[5010];
int main() {
    cin>>n>>FW_number;
    for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];//前缀和
    memset(dp,0x3f,sizeof dp);
    dp[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            if(s[i]-s[j]>=l[j] && dp[i]>dp[j]+(s[i]-s[j])*(s[i]-s[j])) dp[i]=dp[j]+(s[i]-s[j])*(s[i]-s[j]),l[i]=s[i]-s[j];
    write(dp[n]);
    return 0;
}

记录。

单调队列优化

如果 dp_i 由 dp_j 转移，设 p_i=j。

设 s 为 a 的前缀和数组，于是有 l_i=s_i-s_{p_i}。

这个转移的条件有 s_j-s_{p_j}\le s_i-s_j。

移项可得 s_i\ge 2s_j-s_{p_j}。

又因为 s_{i+1}>s_i，所以一个 j 对于 i 满足条件，它对于 i+1 也满足条件。

于是我们建立单调队列，内装候选项。

转移时直接将不满足条件的排出，插入时将比此状态劣（也就是 2s_j-s_{p_j} 大的）的排出。

最后直接计算答案即可。

时间复杂度 O(n)。

注意最后使用 __int128 记录答案，开多了会爆空间，少了会答案错误。

#include<bits/stdc++.h>
using namespace std;
int n,FW_number;
int a[40000010];
long long s[40000010];
inline void write(__int128 x){
    if(x<0){
        putchar('-');
        write(-x);
        return;
    }
    if(x<10){
        putchar(x%10+'0');
        return;
    }
    write(x/10);
    putchar((x%10)^48);
} 

int pre[40000010];
int q[40000010],head,tail;
int b[40000010],p[100010];
inline long long l(int x){
    return s[x]-s[pre[x]];
}
void read(){
    long long x,y,z,m;
    cin>>x>>y>>z>>b[1]>>b[2]>>m;
    for(int i=3;i<=n;i++) b[i]=(x*b[i-1]+y*b[i-2]+z)%(1<<30);
    for(int i=1;i<=m;i++){
        long long l,r;
        cin>>p[i]>>l>>r;
        for(int j=p[i-1]+1;j<=p[i];j++) a[j]=(b[j]%(r-l+1))+l;
    }
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
}
int main() {
    cin>>n>>FW_number;
    if(!FW_number) for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];
    else read();
    head=1,tail=0;
    q[++tail]=0;
    for(int i=1;i<=n;i++){
        while(head<tail && s[i]-s[q[head+1]]>=l(q[head+1])) head++;
        pre[i]=q[head];
        while(head<tail && s[q[tail]]-s[i]>=l(i)-l(q[tail])) tail--;
        q[++tail]=i;
    }
    __int128 ans=0;
    for(int i=n;i;i=pre[i]) ans+=(__int128)l(i)*l(i);
    write(ans);
    return 0;
}