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

Istruggle · 2025-11-26 20:29:03 · 题解

想要项数最多就需要让每一项尽量小，由于要求序列递增，所以需要最后一项最小，令 f_i 表示处理完前 i 个数后最后一个数最小是多少，s_i 为前缀和，则 f_i=\min_{f_j \le s_i-s_j}\{s_i-s_j\}，这样我们就可以从后往前推每一项都是什么，直接做是 \mathcal{O}(n^2) 的，已经可以通过，使用树状数组可以进一步优化到 \mathcal{O}(n \log n)。

AC code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5005;
int n,a[N],s[N],f[N];
vector<int> ans;
signed main(){
    scanf("%lld",&n);
    for(int i = 1;i<=n;i++) scanf("%lld",&a[i]),s[i]=a[i]+s[i-1],f[i]=1e18;
    f[0]=0;
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<i;j++)
        if(f[j]<=s[i]-s[j]) f[i]=min(f[i],s[i]-s[j]);
    }
    int len=0,sum=0,pos=n;
    for(int i = n;i>=1;i--){
        sum+=a[i];
        if(sum==f[pos]){
            len++; pos=i-1;
            ans.push_back(sum); sum=0;
        }
    }
    printf("%lld\n",len);
    for(int i = ans.size()-1;i>=0;i--)
    printf("%lld ",ans[i]);
    return 0;
}