解题思路

暴力枚举

1. 枚举所有断开位置 $k=0\ldots n-1$（按0-based下标处理更方便）。
2. 对于每个 $k$，线性扫描长度为 $n$ 的序列，累加求出$S_k$。
3. 取所有 $S_k$ 的最大值即为答案。

由于 $n\le2000$，双重循环最多做 $4\times10^6$ 次乘加运算，完全可行。

复杂度分析

• 枚举 $k$ 花费 $O(n)$，每次计算 $S_k$ 也花 $O(n)$，总 $O(n^2)$。
  当 $n\le2000$ 时，暴力法即可通过。

代码实现

Python

def max_magic(n, a):
    res = -10**18
    # 枚举断开位置 k（0-based）
    for k in range(n):
        S = 0
        sign = 1  # 用 1 或 -1 表示交替
        # 计算加权交替和
        for j in range(n):
            S += sign * (j+1) * a[(k+j) % n]
            sign *= -1
        res = max(res, S)
    return res

if __name__ == "__main__":
    n = int(input().strip())
    a = list(map(int, input().split()))
    print(max_magic(n, a))

Java

import java.util.*;

public class Main {
    // 计算最大魔法值
    static long maxMagic(int n, int[] a) {
        long ans = Long.MIN_VALUE;
        // 枚举断开位置 k
        for (int k = 0; k < n; k++) {
            long S = 0;
            int sign = 1; // 1 或 -1
            // 计算加权交替和
            for (int j = 0; j < n; j++) {
                S += sign * (long)(j + 1) * a[(k + j) % n];
                sign = -sign;
            }
            ans = Math.max(ans, S);
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        System.out.println(maxMagic(n, a));
        sc.close();
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 计算最大魔法值
long long maxMagic(int n, const vector<int>& a) {
    long long ans = LLONG_MIN;
    // 枚举断开位置 k
    for (int k = 0; k < n; k++) {
        long long S = 0;
        int sign = 1; // 交替符号
        // 加权交替求和
        for (int j = 0; j < n; j++) {
            S += sign * 1LL * (j + 1) * a[(k + j) % n];
            sign = -sign;
        }
        ans = max(ans, S);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cout << maxMagic(n, a) << "\n";
    return 0;
}

题目内容

小红有一个长度为$n$的魔法环,环上依次有数字$a_1,a_2,.,a_n$。她希望通过切开魔法环并对线性序列应用加权

交替求和,得到最终魔法值。操作步骤如下:

1、选定一个断开位置$k(1≦k≦n)$，将环从此位置切开，得到线性序列

$b_1=a_k,b_2=a_{k+1},....$$b_{n-k+1}=a_n,b_{n-k+2}=a1,...,b_n=a_{k-1}$.

2、对得到的线性序列{$bj$}计算加权交替求和:

$S=1·b_1-2·b_2+3·b_3-4·b_4+...+(-1)^{n-1}n·bn$

小红希望在所有可能的断开位置中，$S$的值最大。请你计算并输出此最大值。

输入描述

第一行输入一个整数$n (1≦n≦2000)$，表示魔法环上的数字个数。

第二行输入$n$个整数$a_1,a_2,...,a_n (0≦a_i≦n)$,代表环上各位置的初始数字。

输出描述

输出一个整数，表示小红在所有断开位置的加权交替求和中能获得的最大魔法值。

样例1

输入

4
1 2 3 4

输出

4

说明

当断开位置$k=2$时,序列$[2,3,4,1]$的加权交替求和为 $2-6+12-4=4$,这是所有$S$中的最大值。

样例2

输入

5
1 4 2 3 5

输出

27

说明

当断开位置$k=3$时，序列$[2,3,5,1,4]$的加权交替求和为:

$1×2-2×3+3×5-4×1+5×4=2-6+15-4+20=27$为最大值