专栏文章

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

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mimzx1ad
此快照首次捕获于
2025/12/01 18:17
3 个月前
此快照最后确认于
2025/12/01 18:17
3 个月前
查看原文
想要项数最多就需要让每一项尽量小，由于要求序列递增，所以需要最后一项最小，令 fif_i 表示处理完前 ii 个数后最后一个数最小是多少，sis_i 为前缀和，则 fi=min⁡fj≤si−sj{si−sj}f_i=\min_{f_j \le s_i-s_j}\{s_i-s_j\}，这样我们就可以从后往前推每一项都是什么，直接做是 O(n2)\mathcal{O}(n^2) 的，已经可以通过，使用树状数组可以进一步优化到 O(nlog⁡n)\mathcal{O}(n \log n)。

AC code

CPP
#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;
}

评论

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

正在加载评论...