CF2274B.Prefix

普及-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given an array a1,a2,…,ana_1, a_2, \ldots, a_n.

For each index i=2,3,…,ni = 2, 3, \ldots, n in order, perform the following:

  • Define s=a1+a2+…+ai−1s = a_1 + a_2 + \ldots + a_{i-1}.
  • Replace aia_i with one of the following three values: ai−sa_i - s, aia_i, or ai+sa_i + s.

Over all possible choices, find the maximum value of max⁡(a1,a2,…,an)\max(a_1, a_2, \ldots, a_n) after the process described above.

给你一个数组 a1,a2,…,ana_1, a_2, \ldots, a_n。

按顺序对每个下标 i=2,3,…,ni = 2, 3, \ldots, n 执行以下操作:

  • 定义 s=a1+a2+…+ai−1s = a_1 + a_2 + \ldots + a_{i-1}。
  • 将 aia_i 替换为以下三个值之一:ai−sa_i - s、aia_i 或 ai+sa_i + s。

在所有可能的选择中,求上述过程结束后 max⁡(a1,a2,…,an)\max(a_1, a_2, \ldots, a_n) 的最大可能值。

输入格式

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1041 \le t \le 10^4). The description of the test cases follows.

The first line of each test case contains a single integer nn (2≤n≤502 \le n \le 50).

The second line of each test case contains nn integers a1,a2,…,ana_1, a_2, \ldots, a_n (−50≤ai≤50-50 \le a_i \le 50).

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1041 \le t \le 10^4)。随后是测试用例的描述。

每个测试用例的第一行包含一个整数 nn(2≤n≤502 \le n \le 50)。

每个测试用例的第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n(−50≤ai≤50-50 \le a_i \le 50)。

输出格式

For each test case, output a single integer — the maximum achievable value of max⁡(a1,a2,…,an)\max(a_1, a_2, \ldots, a_n).

Please note that the answer for some test cases won't fit into a 32-bit integer type, so you should use at least a 64-bit integer type in your programming language (like long long in C++).

对于每个测试用例,输出一个整数——max⁡(a1,a2,…,an)\max(a_1, a_2, \ldots, a_n) 可达到的最大值。

请注意,某些测试用例的答案无法用 32 位整数类型表示,因此在编程语言中至少应使用 64 位整数类型(例如 C++ 中的 long long)。

输入输出样例

  • 输入#1

    4
    5
    3 -5 1 -4 2
    2
    -1 2
    3
    1 2 3
    3
    -2 -2 -2

    输出#1

    24
    3
    7
    4

说明/提示

In the first test case, the final array can be made [3,−8,−4,−13,24][3, -8, -4, -13, 24], so the answer is 2424.

In the second test case, for i=2i = 2, s=a1=−1s = a_1 = -1. Replacing a2a_2 with a2−s=2−(−1)=3a_2 - s = 2 - (-1) = 3 gives the answer 33.

In the third test case, the final array can be made [1,3,7][1, 3, 7], so the answer is 77.

In the fourth test case, replacing a2a_2 with a2+s=−4a_2 + s = -4 makes s=−6s = -6 for i=3i = 3. Replacing a3a_3 with a3−s=−2−(−6)=4a_3 - s = -2 - (-6) = 4 gives the final array [−2,−4,4][-2, -4, 4], so the answer is 44.

在第一个测试用例中,最终数组可以变为 [3,−8,−4,−13,24][3, -8, -4, -13, 24],因此答案为 2424。

在第二个测试用例中,当 i=2i = 2 时,s=a1=−1s = a_1 = -1。将 a2a_2 替换为 a2−s=2−(−1)=3a_2 - s = 2 - (-1) = 3,得到答案 33。

在第三个测试用例中,最终数组可以变为 [1,3,7][1, 3, 7],因此答案为 77。

在第四个测试用例中,将 a2a_2 替换为 a2+s=−4a_2 + s = -4,使得 i=3i = 3 时 s=−6s = -6。再将 a3a_3 替换为 a3−s=−2−(−6)=4a_3 - s = -2 - (-6) = 4,得到最终数组 [−2,−4,4][-2, -4, 4],因此答案为 44。

输入解题思路,AI测评打分。不知道怎么写?

首页