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