算法
(贪心、区间DP) $O(N^2)$
显然每次优先安排当前活跃度最大的孩子的移动位置对答案的贡献最大,所以我们可以先给所有孩子的活跃度序列 $A$ 从大到小排序。
每次可以把当前最大值移动到极左或极右,由于没有确定方向,所以需要用区间DP来处理。
记 $P_i$ 表示把第 $i$ 个位置的孩子移动到位置 $P_i$,这样做对答案的贡献就是 $A_i \times |i - P_i|$,而 $|i - P_i| = \max(i - P_i, P_i - i)$
记 dp[i][l][r]
表示左边用了 $l$ 次,右边用了 $r$ 次,得到区间 $[l, r]$,选距离 $i$ 位置较大的极左/极右方向移动所取得的最大值
而 $r = i - l$,所以 DP
的空间可以降下一维
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
using P = std::pair<int, int>;
const int INF = 1e18;
const int MX = 2005;
ll dp[MX][MX];
inline void chmax(ll& a, ll b) { if (a < b) a = b; }
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
rep(i, n + 1)rep(j, n + 1) dp[i][j] = -INF;
dp[0][0] = 0;
vector<P> p;
rep(i, n) p.emplace_back(a[i], i);
sort(p.rbegin(), p.rend());
rep(i, n) {
int pi = p[i].second;
rep(l, i + 1) {
int r = i - l;
chmax(dp[i + 1][l + 1], dp[i][l] + ll(pi - l) * a[pi]);
chmax(dp[i + 1][l], dp[i][l] + ll((n - r - 1) - pi) * a[pi]);
}
}
ll ans = 0;
rep(i, n + 1) chmax(ans, dp[n][i]);
cout << ans << '\n';
return 0;
}