给定 个数 ,现在要将其重排。
如果 于重排前在第 个位置,现在移动到了第 个位置,那么对答案的贡献就是 。
输出所有重排方案中最大的答案。
首先不难发现最大值一定是放在 或者 ,但是会出现放在 和 时价值相同的情况,所以不能直接贪心。
那么考虑设 表示重新排列 后这段区间对答案的最大贡献,但是似乎不太好转移。
继续挖掘性质,不难发现原来的顺序并不重要,考虑从小到大填数。设 表示前 小的数填入 后对答案的最大贡献,转移:
其中 和 分别表示 中第 小的数的位置和数值。
边界为 ,答案为 。
代码如下:
// Problem: [ABC163E] Active Infants
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_abc163_e
// Memory Limit: 1 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int S=2005;
int n,a[S];
int id[S];
long long dp[S][S];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),id[i]=i;
sort(id+1,id+n+1,[&](int x,int y){return a[x]<a[y];});
for(int len=1;len<=n;len++)
{
for(int l=1;l<=n-len+1;l++)
{
int r=l+len-1;
dp[l][r]=max(
dp[l][r-1]+1ll*abs(id[r-l+1]-r)*a[id[r-l+1]],
dp[l+1][r]+1ll*abs(id[r-l+1]-l)*a[id[r-l+1]]
);
}
}
printf("%lld\n",dp[1][n]);
return 0;
}