[Kubic] Addition

题目背景

建议先看 B 题题目背景。

题目描述

有一个初始长度为 $n$ 的序列 $a$。你需要进行 $n-1$ 次操作。每一次操作先在当前序列中选出两个相邻的数 $x,y$ 并删除（原序列中 $x$ 在 $y$ 左边），再往原位置插入一个 $x+y$ 或一个 $x-y$。$n-1$ 次操作之后最终只会剩下恰好一个数，求这个剩下的数的最大值。

输入格式

第一行，一个整数 $n$。

第二行，共 $n$ 个整数 $i$ 个表示 $a_i$。

输出格式

共一行，一个整数，表示答案。

样例 #1

样例输入 #1

5
-1 1 1 -1 1

样例输出 #1

3

提示

对于 $100\%$ 的数据，$1\le n\le 10^5,|a_i|\le 10^9$。

	分值	$n$	$|a_i|$	特殊性质
$\mathrm{Subtask}1$	$10$	$\le 2$	无特殊限制	无
$\mathrm{Subtask}2$	$20$	$\le 100$	无特殊限制	无
$\mathrm{Subtask}3$	$5$	无特殊限制	无特殊限制	$a_i\ge 0$
$\mathrm{Subtask}4$	$30$	无特殊限制	$\le 1$	无
$\mathrm{Subtask}5$	$35$	无特殊限制	无特殊限制	无

样例解释

一种操作过程如下：

-1 1 1 -1 1

-1 1 1 -2

-1 1 3

-1 4

3

可以证明没有更优的方案。

C++实现

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n, x, ans;
signed main()
{
scanf(“%lld%lld”, &n, &x);
ans = x;
for (int i = 2; i <= n; i++)
{
scanf(“%lld”, &x);
ans += x < 0 ? -x : x;
}
printf(“%lld\n”, ans);
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容