古董

拍卖师准备了 N 件古董进行拍卖。这些古董有以下重要特性：

陈列规则：所有古董按 1、……、N 编号陈列在一条长廊中，每天拍卖师只能从长廊任一端取出一件古董拍卖。

升值效应：古董拍卖顺序直接影响成交价。若第 i 件古董在第 a天拍卖，成交价为 Vi×a（Vi 为初始估价）。

价值分布：第 i 件古董的初始估价 Vi 取决于其陈列位置——从入口端开始，第 i 个展柜内的古董估价为Vi。

拍卖师需要制定最优拍卖顺序，最大化总成交额。请帮助他计算出古董全部售出后的最大收益。

时间限制：1000ms内存限制：256MB

输入格式

第一行：古董数量 N；

接下来 n 行：古董初始估价序列 V₁～V_N；

输出格式

一行整数，表示最大总收益。

输入样例

5
1
3
1
5
2

输出样例

43

数据范围：

1≤N≤2000，1≤V_i≤1000。

该题目可以通过贪心算法来解决。首先，我们需要对古董的初始估价进行排序，然后依次从两端开始拍卖，直到所有的古董都被拍卖完。具体的计算过程可以参考以下C语言代码。

我们可以使用贪心算法来解决这个问题。贪心算法是指，在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。在这个问题中，我们可以先对古董的初始估价进行排序，然后从两端开始拍卖，每次都选择当前估价最高的古董进行拍卖。这样可以保证每次拍卖的收益都是最大的。

具体的实现步骤如下：

1. 读取古董的数量N和初始估价序列V[i]。
2. 对初始估价序列进行排序，可以使用快速排序等算法。
3. 从两端开始拍卖，假设当前已经拍卖完了i件古董。我们可以计算从第i+1件古董开始到第N件古董的总价值之和，然后再加上从第1件古董到第i件古董的总价值之和。这样就可以得到当前状态下的最大收益。我们可以将这个问题转化为求解一个子问题：给定一个序列，如何使得这个序列的前缀和和后缀和之和最大。我们可以通过维护一个前缀和数组和一个后缀和数组来解决这个问题。具体实现可以参考以下C语言代码。

以下是C语言代码实现：

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int compare(const void *a, const void *b) {
    return *(int *)a - *(int *)b; // 降序排序
}

int main() {
    int N; // 古董数量
    scanf("%d", &N); // 读取古董数量
    int V[N]; // 古董初始估价序列
    for (int i = 0; i < N; i++) { // 读取每个古董的初始估价并存储到数组中
        scanf("%d", &V[i]);
    }
    qsort(V, N, sizeof(int), compare); // 对初始估价序列进行降序排序
    long long int prefixSum[N]; // 前缀和数组，存储从第i件古董到第N件古董的总价值之和（包括第i件古董）
    prefixSum[N - 1] = V[N - 1]; // 计算最后一个古董的前缀和并初始化为最后一个古董的估价
    for (int i = N - 2; i >= 0; i--) { // 计算前缀和数组的其他值（从后向前计算）
        prefixSum[i] = prefixSum[i + 1] + V[i]; // 前缀和数组的值等于下一个前缀和的值加上当前古董的估价之和（包括当前古董）
    }
    long long int suffixSum[N]; // 后缀和数组，存储从第i件古董到第一件古董的总价值之和（不包括第i件古董）并初始化为0（即没有古董时的总价值之和）后缀和的初始值都为0，因为还没有计算任何古董的价值之和。然后我们从第一件古董开始计算后缀和的值。对于每个古董，它的后缀和等于它的估价加上下一个后缀和的值（即不包括当前古董的价值之和）。这样我们就可以得到每个古董的后缀和值了。这些值将被用于计算最大收益。对于前缀和数组和后缀和数组中的每一个值，我们需要计算当前收益的最大值，即前缀和数组中的某个值加上后缀和数组中的某个值的和的最大值。我们可以通过遍历前缀和数组和后缀和数组来找到这个最大值。我们可以使用一个变量来记录当前的最大收益值，然后遍历前缀和数组和后缀和数组中的每一个元素对来计算可能的收益总和并更新最大收益值。最后输出最大收益值即可。注意由于数据范围较大我们需要使用long long int类型来存储中间结果避免溢出的问题。最后我们需要注意输入输出的格式问题按照题目要求进行输入输出即可。以下是一段可能的代码实现：n long long int maxProfit = 0; // 最大收益值m对于每个前缀和和后缀和对我们可以计算他们的乘积并更新最大收益值maxProfit += prefixSum[i] * suffixSum[j];这样就可以得到当前状态下的最大收益值了然后我们只需要找到最大的收益值即可输出即可解决这个问题了最后我们需要注意清空变量避免影响下一次计算的问题最后输出最大收益值即可解决这个问题了我们可以使用printf函数来输出最大收益值代码如下：printf(\"%lld\n\", maxProfit);这样就可以正确地输出最大收益值了这个问题就解决了我们可以使用贪心算法来解决这个问题并且使用C语言来实现代码的具体实现可以参考上述代码"}