思路
第一次看题很快就能想到贪心。一个大的值无非放到左边和右边，哪边增加的多放到哪边。但是有可能存在两边增加的一样的情况，同时不同的选择会影响以后的数值，所以贪心是错误的。
既然是对后面的数值有影响，那就是明显的 DP。先排个序，从大到小，然后每次先选未选过的最大的，枚举其在左右的两种情况。
DP 方程如下：
\[dp_{l,r} = \max(dp_{l + 1, r} + a_{now} \times |pos_{now} - l|,dp_{l, r - 1} + a_{now} \times |pow_{now} - r|)
\]
代码
重要的事情说三遍：
一定要开 long long！
一定要开 long long！
一定要开 long long！
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2005;
int n;
pair<int, int> a[N];
int f[N][N];
signed main() {
scanf("%lld", &n);
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i].first);
a[i].second = i;
}
sort(a, a + n, greater<pair<int, int>>());
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
int k = i - j;
f[j + 1][k] = max(f[j + 1][k], f[j][k] + a[i].first * abs(a[i].second - j));
f[j][k + 1] = max(f[j][k + 1], f[j][k] + a[i].first * abs(n - k - 1 - a[i].second));
}
}
int ans = 0;
for (int i = 0; i <= n; i++)
ans = max(ans, f[i][n - i]);
printf("%lld", ans);
return 0;
}