作者:
炽热的
,
2022-07-29 00:17:52
,
所有人可见
,
阅读 118
$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;
}