洛谷 4393 序列问题

发表于 | 分类于 | 评论数：

摘要

合并相邻两数的代价是 $max(a_i,a_{i+1})$ ；

考虑一个数做几次贡献。

[BOI2007] Sequence 序列问题

题面

题解

贪心

考虑一个区间中max的贡献，它在区间端点则最少贡献一次，否则最少两次。除去这个max，剩下的区间是子问题。

这给出了一个解的下界，也给出了达到下界的方案。

解的值等于相邻两数max之和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//https://www.luogu.com.cn/problem/P4393
//2021-07-10 AliCCC

#include <cstdio>
#include <algorithm>
using std::max;

const int MAXN=1000111;

int N;
int A[MAXN];


int main(){
	
	scanf("%d", &N);
	for(int i=1;i<=N;++i)	scanf("%d", &A[i]);
	
	long long Ans=0LL;
	for(int i=1;i<N;++i){
		Ans+=max(A[i], A[i+1]);
	}
	printf("%lld\n", Ans);
	
	return 0;
}