专栏文章

题解：SP7741 BOI7SEQ - Sequence

DDLDZD
SP7741题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqz4qpo
此快照首次捕获于
2025/12/04 13:07
3 个月前
此快照最后确认于
2025/12/04 13:07
3 个月前
查看原文

简单贪心

贪心策略

显然，这道题直接写出最优解是困难的，所以我们可以反过来，求最劣解，也就是 max⁡1≤i≤nai×(n−1)\max_{1\le i\le n} a_i \times (n-1)
再反回来，要使得最优，我们最多只能让最大值左边或右边的一个数只和它进行一次操作，再分治，直到区间长度为二即可。最后发现只需要两两枚举，求出最大值之和。
∑i=2nmax⁡(ai,ai−1)\sum_{i=2}^{n} \max \left ( a_i,a_{i-1} \right )

最终实现方法

我们发现，数组可以滚掉一维，用两个变量代替，大大降低了空间复杂度，时间复杂度为 Θ(n)\Theta \left ( n \right ) 。

code

CPP
#include<bits/stdc++.h>
#define int long long 
using namespace std;
signed main(){
	int n,x,y,ans=0;
	cin>>n>>y;
	for(int i=2;i<=n;i++){
		cin>>x;
		ans+=max(x,y);
		y=x;
	}
	cout<<ans;
	return 0;
}//把数组滚掉了

评论

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

正在加载评论...