专栏文章

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

kksmgxeh
P14597题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min0u8u6
此快照首次捕获于
2025/12/01 18:43
3 个月前
此快照最后确认于
2025/12/01 18:43
3 个月前
查看原文
其实就是要求将原序列最多能划分成多少段，使得每段的和单调不降。
一开始是往贪心上去想的，但是思考后发现并没有什么好的策略。于是考虑 dp。设 dpidp_i 表示以 ii 结尾时能划分出的最大段数。这时我们发现无法去比较不同状态间划分出的区间和，于是设 mim_i 为以 ii 结尾的最后一段和的最小值。转移时直接往前枚举上一个合法的结尾 jj，有 dpi=max⁡(dpi,dpj+1)dp_i=\max(dp_i,dp_j+1)，同时更新 mm 的值。再记录一下每次是由谁转移过来的，便于最后输出方案。
至于 mm 的定义为什么是最小值。贪心地想，想让划分的段数越多，那么当前的值越小，可以给后面预留更大的空间，这样肯定不劣。
压行后还是很短的。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...