Codeforces_789C_(dp)
1 second
256 megabytes
standard input
standard output
Something happened in Uzhlyandia again... There are riots on the streets... Famous Uzhlyandian superheroes Shean the Sheep and Stas the Giraffe were called in order to save the situation. Upon the arriving, they found that citizens are worried about maximum values of the Main Uzhlyandian Function f, which is defined as follows:
In the above formula, 1 ≤ l < r ≤ n must hold, where n is the size of the Main Uzhlyandian Array a, and |x| means absolute value of x. But the heroes skipped their math lessons in school, so they asked you for help. Help them calculate the maximum value of f among all possible values of l and r for the given array a.
The first line contains single integer n (2 ≤ n ≤ 10^5) — the size of the array a.
The second line contains n integers a1, a2, ..., an (-10^9 ≤ ai ≤ 10^9) — the array elements.
Print the only integer — the maximum value of f.
5
1 4 2 3 1
3
4
1 5 4 7
6
题意:求公式的最大值。
思路:
b[i]:abs(num[i]-num[i+1]),c[N]:-abs(num[i]-num[i+1]) (i%2==1)
b[i]:-abs(num[i]+num[i+1]),c[N]:abs(num[i]-num[i+1]) (i%2==0)
然后分别求b,c的区间连续最大值,二者中较大着就是答案。
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define LL long long
#define INF 10000000005
int num[N],b[N],c[N]; int main()
{
int n;
scanf("%d",&n);
for(int i=;i<n;i++)
scanf("%d",&num[i]);
for(int i=;i<n-;i++)
{
if(i%)
{
b[i]=abs(num[i]-num[i+]);
c[i]=-abs(num[i]-num[i+]);
}
else
{
b[i]=-abs(num[i]-num[i+]);
c[i]=abs(num[i]-num[i+]);
}
}
LL res1=-INF,res2=-INF,tmp=,l=;
for(int i=;i<n-;i++)
{
tmp+=b[i];
if(tmp>res1)
res1=tmp;
if(tmp<)
tmp=;
}
tmp=;
for(int i=;i<n-;i++)
{
tmp+=c[i];
if(tmp>res2)
res2=tmp;
if(tmp<)
tmp=;
}
printf("%I64d\n",max(res1,res2));
return ;
}
最新文章
- 19-typedef
- Centos 下编译安装Redis
- 有关define定义函数所注意的实例
- linux下mv命令使用方法
- makefile学习小结
- mysql-关于Unix时间戳(unix_timestamp)
- ☆☆配置NDK环境
- equals(),hashcode()方法详解
- 在制作joomla模板过程中遇到的问题
- 【Android实战开发】3G技术和Android发展简介
- Java多线程yield
- Python:开发Sublime插件,方便PHP开发
- java synchronized 线程同步机制详解
- JAVA中Socket的用法模拟服务端和客户端
- dwr3+spring实现消息实时推送
- 自动化服务部署(二):Linux下安装jenkins
- 《Linux内核设计与实现》 第五周 读书笔记(第十八章)
- 设计模式学习--Abstarct Factory
- mybatis中xml文件的${}和#{}区别
- C# 每月第一天和最后一天