YACS 2023年8月月赛甲组 T3 金字塔分割题解

Xy_top / 2023-08-23 / 原文

看到这题，自然的想到 DP 啦！

如果设 $f_{i,j}$ 为到第 $i$ 个位置前面的都合法且最后一段和为 $j$ 是否可行，那么转移十分显然，但是状态会炸。

此时我们考虑在状态上进行优化来减少时间，把 $f_i$ 设为到第 $i$ 个位置分段数量最多的情况下且最后一段和最少的和，以及能分成几段就好了。

不难写出 $n^2$ 的代码：

#include<iostream>
using namespace std;
int n;
int a[200005],s[200005];
int f[200005][2];//满足分段尽可能多的情况下，最后一段和的最小值
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    for(int i=1;i<=n;i++){
        f[i][0]=1;
        f[i][1]=s[i];
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            if(s[i]-s[j]>=f[j][1]&&f[j][0]+1>=f[i][0]){
                if(f[j][0]+1==f[i][0])f[i][1]=min(f[i][1],s[i]-s[j]);
                else{
                    f[i][0]=f[j][0]+1;
                    f[i][1]=s[i]-s[j];
                }
            }
        }
    }
    cout<<f[n][0];
    return 0;
}

接着，我们根据那一行 if 的不等式，进行变换得到 ${s_i}>={s_j}+f_{j,1}$，所以思路显然。

算完 $f_i$ 后，把 $i$ 加到 $s_i+f_{i,1}$ 上，查询就查询 $<=s_i$ 位置上最大的 $f_{x,0}$，如果有多个相同的，那么取 $x$ 最大的，这样一来最后一段的和才能最小。

代码如下：（tjq 说可以单调队列，但对热爱线段树的我来说这样就够了吧。）

#include<iostream>
using namespace std;
const int inf=2000200000;
int n,rt,cnt;
int a[200005],s[200005];
int f[200005][2];//满足分段尽可能多的情况下，最后一段和的最小值
int mx[7000005],ls[7000005],rs[7000005];//单点修改，区间查询
bool cmp(int i,int j){//i 是否比 j 好
    if(i==0)return false;
    if(j==0)return true;
    if(f[i][0]<f[j][0])return false;
    else if(f[i][0]==f[j][0]){
        if(i<j)return false;
        return true;
    }
    return true;
}
void update(int l,int r,int &k,int x,int y){
    if(!k)k=++cnt;
    if(l==r){
        if(!cmp(mx[k],y))mx[k]=y;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)update(l,mid,ls[k],x,y);
    else update(mid+1,r,rs[k],x,y);
    if(cmp(mx[ls[k]],mx[rs[k]]))mx[k]=mx[ls[k]];
    else mx[k]=mx[rs[k]];
}
int query(int l,int r,int k,int x,int y){
    if(x<=l&&y>=r)return mx[k];
    int mid=l+r>>1,res=0;
    if(x<=mid)res=query(l,mid,ls[k],x,y);
    if(y>mid){
        int tmp=query(mid+1,r,rs[k],x,y);
        if(cmp(tmp,res))res=tmp;
    }
    return res;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    for(int i=1;i<=n;i++){
        int j=query(1,inf,1,1,s[i]);
        f[i][0]=f[j][0]+1;
        f[i][1]=s[i]-s[j];
//        for(int j=1;j<i;j++){
//            if(s[i]-s[j]>=f[j][1]&&f[j][0]+1>=f[i][0]){
//                if(f[j][0]+1==f[i][0])f[i][1]=min(f[i][1],s[i]-s[j]);
//                else{
//                    f[i][0]=f[j][0]+1;
//                    f[i][1]=s[i]-s[j];
//                }//s[i]>=s[j]+f[j][1]
//                //算完一个后，将 f[j][0] 的 s[j]+f[j][1] 加到 xds 中，查询 <= s[i] 位置上的最大值
//            }
//        }
        update(1,inf,rt,s[i]+f[i][1],i);
    }
    cout<<f[n][0];
    return 0;
}