Theofanis’ Nightmare

题面翻译

你需要将一个长度为 $n$ 的数列分为若干段。设你分了 $k$ 段，第 $i$ 段的数的和为 $s_i$，你需要最大化 $\sum_{i=1}^ki\times s_i$ 的值。

$n\leq 10^5,|a_i|\leq 10^8$。

题目描述

Theofanis easily gets obsessed with problems before going to sleep and often has nightmares about them. To deal with his obsession he visited his doctor, Dr. Emix.

In his latest nightmare, he has an array $ a $ of size $ n $ and wants to divide it into non-empty subarrays $ ^{\dagger} $ such that every element is in exactly one of the subarrays.

For example, the array $ [1,-3,7,-6,2,5] $ can be divided to $ [1] [-3,7] [-6,2] [5] $ .

The Cypriot value of such division is equal to $ \Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i $ where $ k $ is the number of subarrays that we divided the array into and $ \mathrm{sum}_i $ is the sum of the $ i $ -th subarray.

The Cypriot value of this division of the array $ [1] [-3,7] [-6,2] [5] = 1 \cdot 1 + 2 \cdot (-3 + 7) + 3 \cdot (-6 + 2) + 4 \cdot 5 = 17 $ .

Theofanis is wondering what is the maximum Cypriot value of any division of the array.

$ ^{\dagger} $ An array $ b $ is a subarray of an array $ a $ if $ b $ can be obtained from $ a $ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

Each test case consists of two lines.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^{5} $ ) — the size of the array.

The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ -10^8 \le a_i \le 10^{8} $ ) — the elements of the array.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^{5} $ .

输出格式

For each test case, print one integer — the maximum Cypriot value of the array $ a $ .

样例 #1

样例输入 #1

4
6
1 -3 7 -6 2 5
4
2 9 -5 -3
8
-3 -4 2 -5 1 10 17 23
1
830

样例输出 #1

32
4
343
830

提示

In the first test case, to get the maximum Cypriot value we divide the array into $ [1][-3][7][-6][2][5] $ which gives us: $ \Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i = 1 \cdot 1 + 2 \cdot (-3) + 3 \cdot 7 + 4 \cdot (-6) + 5 \cdot 2 + 6 \cdot 5 = 32 $

Similarly, in the second test case we divide the array into $ [2][9,-5,-3] $ which gives us $ \Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i = 1 \cdot 2 + 2 \cdot (9 + (-5) + (-3)) = 4 $ .

这道题题意挺明白的，我们来考虑一下每次分段的性质。 我们可以发现每次分段的时候，分段的地方之前的答案没有变化，变化的只是之后的答案。

每次分段会使段数增加一个，也就使后面的所有段的排号（每一段的总和乘上的那个数）都会增加一。与之前的式子相比较，整个式子的答案相当于增加了分段的地方的后缀和。所以这道题分段的地方就是所有后缀和为正数的地方，答案便是原数列和加上每次分段的后缀和的总值。

const int N = 2e5 + 10;

int a[N];
int b[N];
int c[N];
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], b[i] = b[i - 1] + a[i];

    int top = 1;
    for (int i = 1; i <= n; i++)
    {
        c[i] = top;
        if (b[n] - b[i] > 0)
        {
            top++;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += a[i] * c[i];
    }
    cout << ans << '\n';
}