【预处理】Codeforces Round #407 (Div. 2) C. Functions again
2024-08-26 23:36:42
考虑枚举每个子串开头的位置,然后答案转化成询问这个位置之后 哪个位置的前缀和 - 这位置的前缀和 最大(当然是已经把绝对值和正负的情况处理好了,可以发现按奇偶,这个序列只有两种情况),只需要预处理这两个序列的前缀和,以及这两个前缀和序列的后缀max即可。
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
int Abs(int x){
return x<0 ? (-x) : x;
}
int n;
int a[100010],b[100010];
ll d[100010],c[100010],e[100010],f[100010],ans;
int main(){
// freopen("c.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
for(int i=1;i<n;++i){
b[i]=Abs(a[i+1]-a[i]);
}
int op=1;
for(int i=1;i<n;++i){
c[i]=c[i-1]+(ll)(b[i]*op);
op=-op;
}
op=-1;
for(int i=1;i<n;++i){
d[i]=d[i-1]+(ll)(b[i]*op);
op=-op;
}
ll maxn=-1e18;
for(int i=n-1;i>=1;--i){
maxn=max(maxn,c[i]);
e[i]=maxn;
}
maxn=-1e18;
for(int i=n-1;i>=1;--i){
maxn=max(maxn,d[i]);
f[i]=maxn;
}
for(int i=1;i<n;i+=2){
ans=max(ans,e[i]-c[i-1]);
}
for(int i=2;i<n;i+=2){
ans=max(ans,f[i]-d[i-1]);
}
cout<<ans<<endl;
return 0;
}
最新文章
- Android中访问sdcard路径的几种方式
- oracle连接问题【转载】
- 【maven】之配置开发,测试,正式环境pom.xml文件
- web服务器长连接
- iOS开发之UITableView使用总结
- python 加密解密(base64, AES)
- C#中的ICollection接口
- struts2关于package 的 namespace
- java中文乱码解决之道(六)—–javaWeb中的编码解码
- [c#]asp.net开发微信公众平台(5)微信图文消息
- 如何在在网页上显示pdf文档
- [Usaco2007 Dec]Building Roads 修建道路[最小生成树]
- androidstudio连接SCM Manager上的Git库
- Android 自定义 ViewPager 打造千变万化的图片切换效果
- [Swift]LeetCode794. 有效的井字游戏 | Valid Tic-Tac-Toe State
- Js修改input值后怎么同步修改绑定的v-model值
- fiddler中断request,修改参数问题
- git撤销中间的某次提交
- 【Java并发核心四】Executor 与 ThreadPoolExecutor
- 源码分析篇 - Android绘制流程(二)measure、layout、draw流程