大意
自己查去...
说明
这道题正解是贪心,但标程里是有这样一句话的:把序列分成(a1,..ai)(ai+1,...aj)......(ak,...an)多个非递减序列。然后所有段中最大值的和减去除第一段外的段的最小值
是否太诡异了呢
于是本oier决定来一个较详细的解析,我们从样例出发
我们会想到先把2层的建好
而下一个是3层的,为了使得区间数最小,我们就把2层时建的区间延伸过去
但三层不够于是单键一层
而后面的放置类似的
观察延伸的过程
当后一个比前一个大时,前一个的区间覆盖不到后一个 答案必须要加上后一个比前一个多的。
当后一个比前一个少时,之前的区间一定可以延伸出去覆盖到它,所以答案只加后一个比前一个大的数。
代码在此
#include<iostream>
#include<cstdio>
using namespace std;
int n,x,p,ans;
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&x);
int k=x-p;
if(k>)ans+=k;
p=x;
}
cout<<ans<<endl;
return ;
}