HDU5805 NanoApe Loves Sequence (BestCoder Round #86 B)前后缀预处理

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了HDU5805 NanoApe Loves Sequence (BestCoder Round #86 B)前后缀预处理，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含777字，纯文字阅读大概需要2分钟。

内容图文

分析：维护空隙的差，然后预处理前缀最大，后缀最大，扫一遍

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
usingnamespace std;
typedef longlong LL;
constint N = 1e5+5;
int a[N],T,n,b[N],l[N],r[N];
int main(){
  scanf("%d",&T);
  while(T--){
   scanf("%d",&n);
   for(int i=1;i<=n;++i)scanf("%d",&a[i]);
   LL ret=0;
   for(int i=1;i<n;++i){
      b[i]=abs(a[i]-a[i+1]);
      l[i]=max(l[i-1],b[i]);
   }
   r[n]=0;
   for(int i=n-1;i>0;--i)r[i]=max(r[i+1],b[i]);
   for(int i=1;i<=n;++i){
     if(i==1)ret+=r[2];
     elseif(i==n)ret+=l[n-2];
     else{
       int tmp=max(l[i-2],r[i+1]);
       tmp=max(tmp,abs(a[i+1]-a[i-1]));
       ret+=tmp;
     }
   }
   printf("%I64d\n",ret);
  } 
  return0;
}

View Code

 

原文：http://www.cnblogs.com/shuguangzw/p/5747415.html

内容总结

以上是互联网集市为您收集整理的HDU5805 NanoApe Loves Sequence (BestCoder Round #86 B)前后缀预处理全部内容，希望文章能够帮你解决HDU5805 NanoApe Loves Sequence (BestCoder Round #86 B)前后缀预处理所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---