题解：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

表示从哪转移，最后倒序输出即可。

CPP

#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

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

文章操作

相关推荐

评论

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