题解：P14597 [COCI 2025/2026 #2] 递增 / Rastući

· · 题解

吐槽 C 题放紫卡我一年/pz

先转化一下题意：

给你一个长为 n 的序列，要划分为若干连续子段使得每段和单调不降，求划分的最大段数。

显然是一个比较经典的 dp。我们设 f_i 表示前 i 个数划分出的最大段数，g_i 表示当前划分下最后一段的最小可能和。f 的定义自不必说，那为什么这样定义 g 呢？其实也很简单，由于单调性只有当最后一段尽量小时后面能分得的段数才更多。

说完了状态再来考虑转移。对于每个 i 我们枚举最后一段的起点 j，记最后一段和为 s，要满足单调性只有 s\le g_j 时才能转移。在所有合法 j 中优选最大的 f_j，若段数相同则选 g_i 更小的（原因前文讲过）。另外需要输出方案所以计一个 pre 表示从哪转移，最后倒序输出即可。

#include <bits/stdc++.h>
#define INF 1e18
using namespace std;
using ll=long long;
int n,a[5010];
ll sum[5010],f[5010],g[5010],pre[5010];
vector<ll> ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        g[i]=INF,pre[i]=-1;
    } 
    g[0]=0;
    for(int i=1;i<=n;++i){
        for(int j=0;j<i;++j){
            ll s=sum[i]-sum[j];
            if(s>=g[j]){
                if(f[i]<f[j]+1 || (f[i]==f[j]+1 && s<g[i])){
                    f[i]=f[j]+1;
                    g[i]=s;
                    pre[i]=j;
                }
            }
        } 
    }
    int i=n;
    while(i){
        int j=pre[i];
        ans.push_back(sum[i]-sum[j]);
        i=j;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans.size()<<"\n";
    for(int i=0;i<ans.size();++i) cout<<ans[i]<<" ";
    return 0;
}

点个赞呗 qaq