题解：P15981 [PA 2026] 堆煎饼 / Stosy naleśników

· · 题解

牛子题。

先考虑全是（不严格）单调递减怎么做，一个显然的做法是把所有单调递减的序列全抽出来，从大到小排序，从大往小取，容易证明这个是对的。

这样的话我们可以把答案拆成两部分，令 f_i 表示在单调递减的序列里取 i 个的最大值，g_i 表示在剩下序列里取 i 的最大值，那么答案显然为 \max_{i=0}^k f_i+g_{k-i}。

然后考虑单调递增怎么做，给出一个引理:

这个证明是容易的，如果有两个序列都取了一部分，由于单调递增的性质，显然是把一个序列取的次数扔到另一个序列最优。

我们将取 i 个物品拆成 qm+r 的形式，选择 q 列完整的，取另外一列中的前 r 个，令 sum_i=\sum_{j=1}^m a_{i,j}，pre_{i,j}=\sum_{k=1}^j a_{i,k}，在取 q 列完整的时候显然是按 sum 从大往小取。

然后剩下了一个 r，那么 r 只有两种选择了：

发现这个式子是前后缀最大值，维护一下：

所以 g_i=g_{qm+r}=\max{(\sum_{i=0}^q sum_i+l_{q,r},\sum_{i=0}^{q+1} sum_i+r_{q,r})}。

然后就没了，里面那个 \sum 也可以前缀和。

代码有点石。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
#define ll long long
#define pii pair<int,int>
#define pb push_back


template<typename T> void chkmin(T& x,T y) {if(y<x) x=y;}
template<typename T> void chkmax(T& x,T y) {if(x<y) x=y;}

int n,m,k;
ll f[N],g[N],ans,ct1;
vector<ll>l[N],r[N];

struct node{
    ll sum;
    vector<ll>a,pre;

    friend bool operator < (node x,node y){
        return x.sum>y.sum;
    }

}b[N];

int ct2;

bool check(int x,vector<ll>a){
    for(int i=1;i<m;i++){
        if(a[i]<a[i+1]) return 0;
    }
    return 1;
}

bool cmp(ll x,ll y){
    return x>y;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin>>n>>m>>k;

    for(int j=0;j<=m;j++){
        l[0].pb(-1e18);
        r[0].pb(-1e18);
    }

    for(int i=1;i<=n;i++){
        ll x;
        vector<ll>a;
        a.pb(0);
        l[i].pb(-1e18);
        r[i].pb(-1e18);
        for(int j=1;j<=m;j++){
            l[i].pb(-1e18);
            r[i].pb(-1e18);
            cin>>x;
            a.pb(x);
        }
        if(check(i,a)){
            for(auto t:a){
                if(t) f[++ct1]=t;
            }
        }
        else{
            b[++ct2]={0,a};
        }
    }

    sort(f+1,f+1+ct1,cmp);
    for(int i=1;i<=ct1;i++) f[i]+=f[i-1];

    for(int i=1;i<=ct2;i++){
        ll p=0;
        for(auto x:b[i].a){
            p+=x;
            b[i].pre.pb(p);
        }
        b[i].sum=b[i].pre[m];
    }

    sort(b+1,b+1+ct2);

    // cout<<ct2<<'\n';

    for(int j=1;j<=m;j++){
        for(int i=ct2-1;i>=0;i--){
            l[i][j]=max(l[i+1][j],b[i+1].pre[j]);
        }
        for(int i=1;i<=ct2;i++){
            r[i][j]=max(r[i-1][j],b[i].pre[j]-b[i].sum);
        }
    }

    ll sum=0;

    for(int t=0;t<=ct2;t++){
        sum+=b[t].sum;
        for(int p=0;p<=m;p++){
            chkmax(g[t*m+p],sum+l[t][p]);
            chkmax(g[t*m+p],sum+b[t+1].sum+r[t][p]);
        }
    }

    for(int i=0;i<=k;i++) chkmax(ans,f[i]+g[k-i]);

    // cout<<f[i]<<' '<<g[i]<<'\n',

    cout<<ans<<'\n';

    return 0;
}