$f(i, j)$ 表示队头弹出了 $i$ 个元素， 队尾弹出了 $j$ 个元素的最大价值

状态转移

• 是根据最后一次弹的是对头还是对尾划分
• 最后一次弹出的是队头：$f(i - 1, j) + (i + j) * a_i$
• 最后一次弹出的是队尾：$f(i, j - 1) + (i + j) * b_j$

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2010, M = N / 2;

int n;
int a[N], b[N];
long long f[N][N];

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        b[n - i + 1] = a[i];
    }

    for (int i = 1; i <= n; i ++ ) f[i][0] = f[i - 1][0] + a[i] * i;
    for (int i = 1; i <= n; i ++ ) f[0][i] = f[0][i - 1] + b[i] * i;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n - i; j ++ )
            f[i][j] = max(f[i][j - 1] + (i + j) * b[j], f[i - 1][j] + (i + j) * a[i]);

    long long res = 0;
    for (int i = 0; i <= n; i ++ ) res = max(res, f[i][n - i]);

    cout << res << endl;        

    return 0;
}