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

· · 题解

其实就是要求将原序列最多能划分成多少段，使得每段的和单调不降。

一开始是往贪心上去想的，但是思考后发现并没有什么好的策略。于是考虑 dp。设 dp_i 表示以 i 结尾时能划分出的最大段数。这时我们发现无法去比较不同状态间划分出的区间和，于是设 m_i 为以 i 结尾的最后一段和的最小值。转移时直接往前枚举上一个合法的结尾 j，有 dp_i=\max(dp_i,dp_j+1)，同时更新 m 的值。再记录一下每次是由谁转移过来的，便于最后输出方案。

至于 m 的定义为什么是最小值。贪心地想，想让划分的段数越多，那么当前的值越小，可以给后面预留更大的空间，这样肯定不劣。

压行后还是很短的。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 5005;
int n,a[N],f[N],pre[N];
ll s[N],m[N],b[N];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    // freopen("test.in","r",stdin);

    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++)
        for(int j=i-1;j>=0;j--)
            if(s[i]-s[j]>=m[j])
                if(f[i]<f[j]+1)
                    f[i]=f[j]+1,m[i]=s[i]-s[j],pre[i]=j;
    cout<<f[n]<<"\n";
    int now=n,cnt=0;
    while(now) b[++cnt]=s[now]-s[pre[now]],now=pre[now];
    for(int i=cnt;i;i--) cout<<b[i]<<' ';
    return 0;
}