P1969 积木大赛
斯德哥尔摩
2018-10-21 12:32:36
[P1969 积木大赛](https://www.luogu.org/problemnew/show/P1969)
首先想到的是暴力：
依次读入每个高度，并从$1-h$枚举同一高度，并与上一个同一高度的标记值比较，只要标记值为$0$或者差值大于$1$就会增加一次移动次数，并更新标记一次。
但一看数据规模——$n<=10^5,h_i<=10^4$。。。
这不是笋干爆炸的节奏么。。。
于是想优化。
我们发现我们其实就是把序列分成$[1,i]\bigcup [i+1,j]\bigcup ...\bigcup [k,n]$这些**非递减**序列区间。
然后所有区间中最大值的和减去除第一段外的段的最小值即可。
当然，我化简了一下。。。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 100010
using namespace std;
int n,ans=0;
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void work(){
int last=0;
n=read();
for(int i=1;i<=n;i++){
int x=read();
if(x>last)ans+=(x-last);
last=x;
}
printf("%d\n",ans);
}
int main(){
work();
return 0;
}
```