大意

自己查去...

说明

这道题正解是贪心,但标程里是有这样一句话的:把序列分成(a1,..ai)(ai+1,...aj)......(ak,...an)多个非递减序列。然后所有段中最大值的和减去除第一段外的段的最小值

是否太诡异了呢

于是本oier决定来一个较详细的解析,我们从样例出发

NOIP2013积木大赛 [贪心]-LMLPHP

我们会想到先把2层的建好

NOIP2013积木大赛 [贪心]-LMLPHP而下一个是3层的,为了使得区间数最小,我们就把2层时建的区间延伸过去NOIP2013积木大赛 [贪心]-LMLPHP

但三层不够于是单键一层NOIP2013积木大赛 [贪心]-LMLPHP

而后面的放置类似的NOIP2013积木大赛 [贪心]-LMLPHP

观察延伸的过程

当后一个比前一个大时,前一个的区间覆盖不到后一个 答案必须要加上后一个比前一个多的。

当后一个比前一个少时,之前的区间一定可以延伸出去覆盖到它,所以答案只加后一个比前一个大的数。

代码在此

#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 ;
}
05-11 13:22
查看更多