http://codeforces.com/contest/789/problem/C

首先按题目要求处理出dis数组。

那么对于任意一个区间,[L, R],是dis[L] - dis[L + 1] + dis[L + 2] .... +

那么怎么知道是+还是—呢?

注意到对于一个数,要么是正,要么是负。

考虑第一个数,是正的时候,第三个数肯定是取正,第二个数肯定只能是负。

那么就是对这个数组求一次最大字段和

同理第一个数是负数的情况。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 1e5 + ;
LL a[maxn], dis[maxn];
LL dp[maxn];
void work() {
int n;
cin >> n;
for (int i = ; i <= n; ++i) cin >> a[i];
LL ans = ;
for (int i = ; i <= n - ; ++i) {
dis[i] = abs(a[i] - a[i + ]);
}
for (int i = ; i <= n - ; i += ) {
dis[i] = -dis[i];
}
for (int i = ; i <= n - ; ++i) {
dp[i] = max(dp[i - ] + dis[i], dis[i]);
ans = max(ans, dp[i]);
}
memset(dp, , sizeof dp);
for (int i = ; i <= n - ; i += ) {
dis[i] = -dis[i];
}
for (int i = ; i <= n - ; i += ) {
dis[i] = -dis[i];
}
for (int i = ; i <= n - ; ++i) {
dp[i] = max(dp[i - ] + dis[i], dis[i]);
ans = max(ans, dp[i]);
}
cout << ans << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}

最新文章

  1. navicat 连接 oracle
  2. jQuery UI常用插件使用
  3. java 方法调用绑定
  4. JQuery EasyUI中datagrid的使用
  5. dubbo源码之四——dubbo服务发布
  6. Flask + Gunicorn + Nginx 部署
  7. 12. Android框架和工具之 StringUtils(字符串操作)
  8. PowerDesigner中转换物理模型时的命名转换
  9. Machine Learning—Mixtures of Gaussians and the EM algorithm
  10. Linux的常用基本命令。
  11. NLTK学习笔记(三):NLTK的一些工具
  12. mysql主从配置主主配置
  13. SQL 数据库连续插入大批量数据时超时
  14. bzoj 1558: [JSOI2009]等差数列
  15. Vue 使用axios获取数据
  16. WDS 三种模式
  17. thinkphp3.2自定义success及error跳转页面
  18. (C/C++学习笔记) 二十四. 知识补充
  19. 甲题题解-1116. Come on! Let’s C (20)-(素数筛选法)
  20. python3 str.format()的使用

热门文章

  1. python berkeley 操作——尤其提示 需版本匹配
  2. 图片轮播和C3动画
  3. bzoj 1098 [POI2007]办公楼biu——链表
  4. vijos1842(火柴排队)
  5. socket学习目录
  6. Httpclient入门代码
  7. 【eclipse插件开发实战】 Eclipse插件开发6——eclipse在线翻译插件Translator开发实例详解
  8. 计算机图形学DDA画线法+中点画线法+Bresenham画线法
  9. Tomcat 容器的安全认证和鉴权
  10. 3DMAX 如何将删去的面补回来